CF1797F.Li Hua and Path

Li Hua has a tree of $n$ vertices and $n-1$ edges. The vertices are numbered from $1$ to $n$.

A pair of vertices $(u,v)$ ($u \lt v$) is considered cute if exactly one of the following two statements is true:

• $u$ is the vertex with the minimum index among all vertices on the path $(u,v)$.
• $v$ is the vertex with the maximum index among all vertices on the path $(u,v)$.

There will be $m$ operations. In each operation, he decides an integer $k_j$, then inserts a vertex numbered $n+j$ to the tree, connecting with the vertex numbered $k_j$.

He wants to calculate the number of cute pairs before operations and after each operation.

Suppose you were Li Hua, please solve this problem.

李华有一棵包含 $n$ 个顶点和 $n-1$ 条边的树。顶点编号为 $1$ 到 $n$。

若一对顶点 $(u,v)$（满足 $u \lt v$）恰好满足以下两个命题中的一个为真，则称其为“可爱对”：

• $u$ 是路径 $(u,v)$ 上所有顶点中编号最小的顶点；
• $v$ 是路径 $(u,v)$ 上所有顶点中编号最大的顶点。

接下来将进行 $m$ 次操作。每次操作中，他选定一个整数 $k_j$，并向树中插入一个编号为 $n+j$ 的新顶点，并将其与编号为 $k_j$ 的顶点相连。

他希望计算初始时（所有操作前）以及每次操作后的“可爱对”的数量。

假设你是李华，请解决该问题。

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 \lt n+j$) — a vertex.

第一行包含一个整数 $n$（$2\le n\le 2\cdot 10^5$）——树中顶点的数量。

接下来的 $n-1$ 行描述树的边。第 $i$ 行包含两个整数 $u_i$ 和 $v_i$（$1\le u_i,v_i\le n$；$u_i\ne v_i$）——对应的一条边。所给的边构成一棵树。

接下来一行包含一个整数 $m$（$1\le m\le 2\cdot 10^5$）——操作的数量。

接下来的 $m$ 行每行描述一个操作。第 $j$ 个操作包含一个整数 $k_j$（$1\le k_j \lt n+j$）——一个顶点。

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

输出 $m+1$ 个整数——分别为操作前以及每次操作后的“可爱对”数量。

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$.

初始树如下图所示：

共有 $11$ 个“可爱对”——$(1,5),(2,3),(2,4),(2,6),(2,7),(3,4),(3,6),(3,7),(4,5),(5,7),(6,7)$。

类似地，我们可以统计每次操作后的“可爱对”数量，结果分别为 $15$ 和 $19$。