Under construction

Still being built. Things may change

The Quest for the Sacred Groves

Time limit1sMemory limit2048 MB

Summary
Given a tree on n vertices and a permutation p, count the subarrays of p whose vertices form a connected subgraph of the tree.
Level

Medium6 of 10

Topics
Segment tree, Tree, Implementation
Solved
No attempts yet

Background

In the heart of ancient Romania, where dense forests meet towering mountains, lies the enchanted kingdom of Vatra Codrilor. The kingdom is protected by nn sacred groves, numbered from 11 to nn, and each grove is watched over by a guardian spirit. The groves are connected by secret paths known only to the wise elders. Formally, the secret paths form a tree.

One night, as the full moon rises, the nn guardians receive a divine message from the Dacian gods. The message is an ancient scroll with a list pp. Formally, pp is a sequence of length nn in which every number from 11 to nn appears exactly once. The list gives the order in which the guardians must stand in the final battle.

Task

For each subsegment [ℓ,r][\ell, r] of the list, if the groves pℓ,pℓ+1,…,prp_{\ell}, p_{\ell+1}, \ldots, p_{r} are connected through the secret paths without involving any other groves, the guardians of these groves can meet together and draw on the power of the forest.

Count the number of subsegments [ℓ,r][\ell, r] with 1≤ℓ≤r≤n1 \leq \ell \leq r \leq n that have this property.

Input

The first line contains an integer nn (1≤n≤2⋅1051 \leq n \leq 2 \cdot 10^5).

Each of the next n−1n - 1 lines contains two integers uiu_i and viv_i (1≤ui,vi≤n1 \leq u_i, v_i \leq n), denoting an edge of the tree.

The last line contains the nn distinct integers p1,p2,…,pnp_1, p_2, \ldots, p_n (1≤pi≤n1 \leq p_i \leq n).

Output

Print a single integer: the number of subsegments [ℓ,r][\ell, r] with 1≤ℓ≤r≤n1 \leq \ell \leq r \leq n such that the groves pℓ,pℓ+1,…,prp_{\ell}, p_{\ell+1}, \ldots, p_{r} form a connected subgraph.

Examples2

  1. Example 1

    Input
    7
    1 2
    1 3
    3 4
    3 5
    3 6
    2 7
    7 3 4 1 2 5 6
    
    Expected output
    16
    
  2. Example 2

    Input
    7
    1 2
    1 3
    3 4
    3 5
    3 6
    2 7
    7 2 4 1 3 5 6
    
    Expected output
    22