Hai sa facem si noi ceva #4 | Connected

You are given an undirected tree with $N$ vertices, numbered from $1$ to $N$ (a tree is an undirected connected graph in which there are no cycles) and a permutation $P$ of its nodes (a sequence of length $N$, arranged in any order and no node number appears twice in the sequence).

Task

You are asked to compute the number of contiguous subsequences $[l, r]$ ($1 \leq l \leq r \leq N$) of $P$ such that the nodes $P_l,P_{l+1},\dots,P_r$ form a connected undirected graph.

Input data

The first line contains an integer $N$.
The next $N − 1$ lines contain 2 integers $u_i$, $v_i$, denoting an edge of the tree.
The last line of the input contains the $N$ numbers $P_1, P_2, \dots, P_N$, representing the permutation $P$.

Output data

You need to write a single line with an integer: the number of contiguous subsequences $[l, r]$ ($1 \leq l \leq r \leq N$) of $P$ such that the nodes $P_l, P_{l+1}, \dots, P_r$ form a connected undirected graph.

Constraints and clarifications

• $1 \leq N \leq 2 \cdot 10^{5}$
• $1 \leq u_i, v_i \leq N$

Example

stdin

5
1 2
1 3
2 4
2 5
1 2 4 3 5

stdout

10

Explanation

In the sample case, one example of a contiguous subsequence of nodes which forms a connected region is the one formed by the first $4$ elements of $P$. One example of a subrange of nodes from $P$ which does not form a connected region is $2, 4, 3$.