Li Hua and Path

Description:

Input:

The first line contains the single integer $$$n$$$ ($$$2\le n\le 2\cdot 10^5$$$) — the number of vertices in the tree.

Next $$$n-1$$$ lines contain the edges of the tree. The $$$i$$$-th line contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1\le u_i,v_i\le n$$$; $$$u_i\ne v_i$$$) — the corresponding edge. The given edges form a tree.

The next line contains the single integer $$$m$$$ ($$$1\le m\le 2\cdot 10^5$$$) — the number of operations.

Next $$$m$$$ lines contain operations — one operation per line. The $$$j$$$-th operation contains one integer $$$k_j$$$ ($$$1\le k_j < n+j$$$) — a vertex.

Output:

Print $$$m+1$$$ integers — the number of cute pairs before operations and after each operation.

Sample Input:

7
2 1
1 3
1 4
4 6
4 7
6 5
2
5
6

Sample Output:

11
15
19

Note:

The initial tree is shown in the following picture:

There are $$$11$$$ cute pairs — $$$(1,5),(2,3),(2,4),(2,6),(2,7),(3,4),(3,6),(3,7),(4,5),(5,7),(6,7)$$$.

Similarly, we can count the cute pairs after each operation and the result is $$$15$$$ and $$$19$$$.