25696번 - Smaller LCA 다국어

Grammy has a tree with vertices numbered from $1$ to $n$. For each vertex as the root, she wants to know how many unordered pairs of points $(x, y)$ have their lowest common ancestor $z$ satisfy the inequality $z \leq x \cdot y$. Please count it for her.

The first line contains a single integer $n$ ($1 \leq n \leq 300\,000$), denoting the number of vertices of the tree.

Each of the next $n-1$ lines contains two integers $u_i$ and $v_i$ ($1 \leq u_i, v_i \leq n$), indicating that there is an edge between vertex $u_i$ and vertex $v_i$. It is guaranteed that the given graph is a tree.

Output $n$ lines. The $i$-th line must contain a single integer: the number of pairs satisfying the condition when vertex $i$ is the root.