No.1098 LCAs
SSRS
しのProblem Statement
There is a rooted tree with $N$ vertices.
The vertices of the rooted tree are numbered from $1$ to $N$, and the root is vertex $1$. The $i (1 \leq i < N)$-th edge connects vertex $v_i$ and vertex $w_i$ bidirectionally.
For each $k=1,2,\cdots,N$, solve the following problem.
- Find the number of pairs $(v,w)$ of two vertices of the tree whose lowest common ancestor (LCA) is vertex $k$.
Input
$N$
$v_1 \ w_1$
$v_2 \ w_2$
$\vdots$
$v_{N-1} \ w_{N-1}$
The input satisfies the following constraints.
- All input values are integers.
- $1 \leq N \leq 2\times10^5$
- $1 \leq v_i, w_i \leq N (1 \leq i < N)$
- The given graph is a tree.
Output
Output $N$ lines.
On the $i (1 \leq i \leq N)$-th line, output the answer for $k=i$.
Sample
Sample 1
Input
3 1 2 1 3
Output
7 1 1
The pairs $(v,w)$ such that the LCA of vertex $v$ and vertex $w$ is vertex $1$ are the $7$ pairs $(1,1), (1,2), (1,3), (2,1), (2,3), (3,1), (3,2)$.
The only pair $(v,w)$ such that the LCA of vertex $v$ and vertex $w$ is vertex $2$ is the $1$ pair $(2,2)$.
The only pair $(v,w)$ such that the LCA of vertex $v$ and vertex $w$ is vertex $3$ is the $1$ pair $(3,3)$.
Therefore, the answers for $k=1,2,3$ are $7,1,1$, respectively.
Sample 2
Input
5 1 2 2 3 3 4 3 5
Output
9 7 7 1 1
Sample 3
Input
1
Output
1
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。