{"raw_statement":[{"iden":"problem statement","content":"You are given a tree $T$ with $N$ vertices: vertex $1$, vertex $2$, $\\ldots$, vertex $N$. The $i$\\-th edge $(1\\leq i\\lt N)$ connects vertices $u_i$ and $v_i$.\nFor a vertex $u$ in $T$, define $f(u)$ as follows:\n\n*   $f(u)\\coloneqq$ The number of pairs of vertices $v$ and $w$ in $T$ that satisfy the following two conditions:\n    *   Vertex $w$ is contained in the path connecting vertices $u$ and $v$.\n    *   $v\\lt w$.\n\nHere, vertex $w$ is contained in the path connecting vertices $u$ and $v$ also when $u=w$ or $v=w$.\nFind the values of $f(1),f(2),\\ldots,f(N)$."},{"iden":"constraints","content":"*   $2\\leq N\\leq2\\times10^5$\n*   $1\\leq u_i\\leq N\\ (1\\leq i\\leq N)$\n*   $1\\leq v_i\\leq N\\ (1\\leq i\\leq N)$\n*   The given graph is a tree.\n*   All input values are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$\n$u_1$ $v_1$\n$u_2$ $v_2$\n$\\vdots$\n$u_{N-1}$ $v_{N-1}$"},{"iden":"sample input 1","content":"7\n1 2\n2 3\n2 4\n4 5\n4 6\n6 7"},{"iden":"sample output 1","content":"0 1 3 4 8 9 15\n\nThe given tree is as follows:\n![image](https://img.atcoder.jp/abc337/f02c6287abee93272dda64faf9499a81.png)\nFor example, $f(4)=4$. Indeed, for $u=4$, four pairs $(v,w)=(1,2),(1,4),(2,4),(3,4)$ satisfy the conditions."},{"iden":"sample input 2","content":"15\n14 9\n9 1\n1 6\n6 12\n12 2\n2 15\n15 4\n4 11\n11 13\n13 3\n3 8\n8 10\n10 7\n7 5"},{"iden":"sample output 2","content":"36 29 32 29 48 37 45 37 44 42 33 36 35 57 35\n\nThe given tree is as follows:\n![image](https://img.atcoder.jp/abc337/e59ed095480b6f8ec4ecfc212f14e635.png)\nThe value of $f(14)$ is $57$, which is the inversion number of the sequence $(14,9,1,6,12,2,15,4,11,13,3,8,10,7,5)$."},{"iden":"sample input 3","content":"24\n7 18\n4 2\n5 8\n5 15\n6 5\n13 8\n4 6\n7 11\n23 16\n6 18\n24 16\n14 21\n20 15\n16 18\n3 16\n11 10\n9 11\n15 14\n12 19\n5 1\n9 17\n5 22\n11 19"},{"iden":"sample output 3","content":"20 20 41 20 21 20 28 28 43 44 36 63 40 46 34 40 59 28 53 53 66 42 62 63"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}