Counting Connected Point Sets on a Tree

Given a tree with n nodes, we define a point set to be connected if and only if there exists a simple path in the tree that covers this set and the size of the set is at least 2. In other words, a set of vertices is connected if all of them lie on some simple path in the tree.

Your task is to compute, for every vertex, the number of connected point sets (of size at least 2) that contain that vertex.

Note that any two distinct vertices always lie on a unique simple path. However, three or more vertices are connected only if they are collinear on some simple path. Hence, every connected point set is uniquely determined by choosing two endpoints and taking all vertices on the simple path between them.

The total number of simple paths in a tree is \(\binom{n}{2}\). For a given vertex \(v\), if removing \(v\) splits the tree into several connected components of sizes \(s_1, s_2, \dots, s_k\), then the number of paths that do not pass through \(v\) is \(\sum_{i=1}^{k} \binom{s_i}{2}\). Thus, the number of connected point sets that contain vertex \(v\) is given by:

$$ answer_v = \binom{n}{2} - \sum_{i=1}^{k} \binom{s_i}{2} $$

inputFormat

The input begins with a single integer n (2 ≤ n ≤ 10⁵), representing the number of nodes in the tree. The next n - 1 lines each contain two integers u and v (1 ≤ u, v ≤ n) indicating that there is an undirected edge connecting nodes u and v.

outputFormat

Output a single line containing n space-separated integers. The i-th integer denotes the number of connected point sets (of size at least 2) that contain vertex i.

sample

3
1 2
2 3

2 3 2