Li Hua and Path
Contest: Codeforces Round 864 (Div. 2)
Difficulty rating: 3000
Tags: data structures, dfs and similar, divide and conquer, dsu, trees

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

Input format:
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 format:
Print $$$m+1$$$ integers — the number of cute pairs before operations and after each operation.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

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

Example input:
7
2 1
1 3
1 4
4 6
4 7
6 5
2
5
6

Example output:
11
15
19

Editorial:
There exists an acceptable $$$O(n\log^2n+m)$$$ solution using centroid decomposition, but there is a better $$$O(n\log n+m)$$$ solution using reconstruction trees.
The initial tree is shown in the following picture:
Consider the following reconstruction trees. We will define two reconstruction trees called min-RT and max-RT where "RT" means reconstruction tree.
For the max-RT, we enumerate vertices in increasing order. We create a new vertex $$$u$$$ in the max-RT, then find each vertex $$$v$$$ such that $$$v < u$$$ and $$$v$$$ is adjacent to $$$u$$$ in the original tree, make $$$u$$$ become the father of the root of $$$v$$$ on the max-RT. We can use a dsu to build the max-RT.
The max-RT is shown in the following picture:
The property that $$$\operatorname{LCA}(u, v)$$$ on the max-RT is the maximum index on the path between $$$(u,v)$$$ on the original tree is satisfied.
The min-RT is similar to the max-RT.
The min-RT is shown in the following picture:
After designing the reconstruction trees, I found out that the reconstruction trees are related to Kruskal reconstruction trees (KRT) to a certain extent. Here is another way to understand the two reconstruction trees. For the max-RT, since we want to calculate the maximum index on the path, we define the weight of an edge $$$(u,v)$$$ as $$$\max\{u,v\}$$$. We build a (minimum spanning) KRT of the original tree and merge the vertices with the same weight into one vertex. For the min-RT, define the weight of an edge $$$(u,v)$$$ as $$$\min\{u,v\}$$$ and use the (maximum spanning) KRT.
The max-RT and the (minimum spanning) KRT: (left: maximum valued graph; middle: KRT; right: max-RT)
The min-RT and the (maximum spanning) KRT: (left: minimum valued graph; middle: KRT; right: min-RT)
We will solve the problem using the two reconstruction trees. Let's call the two restrictions in the statement I and II.
Denote $$$K$$$ as the number of pairs satisfying exactly one of I and II (which is the answer), $$$A$$$ as the number of pairs satisfying I, $$$B$$$ as the number of pairs satisfying II and $$$C$$$ as the number of pairs satisfying both I and II. It's obvious that $$$K=A+B-2C$$$.
We can easily calculate $$$A$$$ and $$$B$$$ using the depth of each vertex on two reconstruction trees. Due to the property mentioned above, $$$C$$$ is the number of pairs $$$(u,v)$$$ satisfying the condition that $$$u$$$ is an ancestor of $$$v$$$ on min-RT and $$$v$$$ is an ancestor of $$$u$$$ on max-RT, which can be solved using dfs order and Fenwick tree.
Finally, we calculated the original answer. If we add a vertex with the largest index as a leaf, paths ending with this vertex will satisfy II, so we can use min-RT to calculate the paths ending with this vertex not satisfying I and update the answer.
Time complexity: $$$O(n\log n+m)$$$.