409763: GYM103736 D Tree Problem

You are given a tree consisting of $$$n$$$ vertices. Recall that a tree is a connected graph consisting of $$$n$$$ vertices and $$$(n-1)$$$ undirected edges.

Now, your task is to answer $$$q$$$ queries. Each query will give you a vertex $$$x$$$, please calculate the number of simple paths of length at least one through the vertex $$$x$$$. Note that paths that differ only by their direction are considered the same (i. e. you have to calculate the number of undirected paths). For example, paths $$$[1,2,3]$$$ and $$$[3,2,1]$$$ are considered the same.

Recall that a simple path is a path that visits each vertex at most once.

The first line contains an integer $$$n$$$ $$$(2 \leq n \leq 10^5)$$$ indicating the number of vertices.

For the next $$$(n-1)$$$ lines, the $$$i$$$-th line contains two integers $$$u_i$$$ and $$$v_i$$$ $$$(1 \leq u_i, v_i \leq n)$$$ indicating an edge connecting vertices $$$u_i$$$ and $$$v_i$$$ in the tree.

The first line contains an integer $$$q$$$ $$$(1 \leq q \leq 10^5)$$$ indicating the number of queries.

For the next $$$q$$$ lines, the $$$i$$$-th line contains an integer $$$x_i$$$ $$$(1 \leq x_i \leq n)$$$ indicating the vertex as described above.

For each query output one line containing one integer indicating the answer.

5
1 2
1 3
3 4
3 5
5
1
2
3
4
5

7
4
9
4
4

The example looks like that:

There are $$$7$$$ different simple paths through vertex $$$1$$$:

• $$$[1, 2]$$$;
• $$$[1, 3]$$$;
• $$$[2, 1, 3]$$$;
• $$$[1, 3, 4]$$$;
• $$$[1, 3, 5]$$$;
• $$$[2, 1, 3, 4]$$$;
• $$$[2, 1, 3, 5]$$$.