409763: GYM103736 D Tree Problem
Description
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.
InputThe 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.
OutputFor each query output one line containing one integer indicating the answer.
ExampleInput5 1 2 1 3 3 4 3 5 5 1 2 3 4 5Output
7 4 9 4 4Note
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]$$$.