Tree on the Line
Limits: 2 sec., 256 MiB
Zenyk has a tree of \(n\) vertices numbered from 1 to \(n\), inclusive.
Marichka has a permutation \(p\) of integers from 1 to \(n\), inclusive.
One day they got interested in the answer to the following question. How many ranges \([l, r]\) exist \((1 \le l \le r \le n)\), such that vertices \(p_l, p_{l+1}, ..., p_{r}\) form a connected subgraph of the Zenyk’s tree?
Help them and find the answer.
Input
The first line contains a single integer \(n\).
The second line contains \(n\) space-separated integers \(p_1, ..., p_n\) — the permutation Marichka has.
The next \(n-1\) lines describe edges of the tree Zenyk has. Each line contains a pair of vertex indices that the corresponding edge connects.
Output
In the only line print the answer to the problem.
Constraints
\(1 \le n \le 10^5\).
Samples
Input (stdin) | Output (stdout) |
---|---|
5 1 5 3 2 4 3 5 5 1 1 4 2 1 | 10 |
Submit a solution
Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
---|
Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
---|