{"problem":{"name":"Tree Inversion","description":{"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$. For a vertex $u$ in $T$, define $f(u)$ as","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc337_g"},"statements":[{"statement_type":"Markdown","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)$.\n\n## Constraints\n\n*   $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.\n\n## Input\n\nThe 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}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc337_g","tags":[],"sample_group":[["7\n1 2\n2 3\n2 4\n4 5\n4 6\n6 7","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."],["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","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)$."],["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","20 20 41 20 21 20 28 28 43 44 36 63 40 46 34 40 59 28 53 53 66 42 62 63"]],"created_at":"2026-03-03 11:01:14"}}