Connected

Time limit: 0.65s Memory limit: 64MB Input: Output:

You are given an undirected tree with NN vertices, numbered from 11 to NN (a tree is an undirected connected graph in which there are no cycles) and a permutation PP of its nodes (a sequence of length NN, 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][l, r] (1lrN1 \leq l \leq r \leq N) of PP such that the nodes Pl,Pl+1,,PrP_l,P_{l+1},\dots,P_r form a connected undirected graph.

Input data

The first line contains an integer NN.
The next N1N − 1 lines contain 2 integers uiu_i, viv_i, denoting an edge of the tree.
The last line of the input contains the NN numbers P1,P2,,PNP_1, P_2, \dots, P_N, representing the permutation PP.

Output data

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

Constraints and clarifications

  • 1N21051 \leq N \leq 2 \cdot 10^{5}
  • 1ui,viN1 \leq u_i, v_i \leq N
# Points Constraints
1 10 1N2001 \leq N \leq 200
2 20 1N2 0001 \leq N \leq 2\ 000
3 30 The given tree is just a simple chain.
4 40 No additional constraints.

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 44 elements of PP. One example of a subrange of nodes from PP which does not form a connected region is 2,4,32, 4, 3.

Log in or sign up to be able to send submissions!