{"problem":{"name":"Ex - Balanced Tree","description":{"content":"You are given a tree $T$ with $N$ vertices. The $i$\\-th edge connects vertices $A_i$ and $B_i$. Construct an $N$\\-vertex rooted tree $R$ that satisfies the following conditions. *   For all integer p","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc291_h"},"statements":[{"statement_type":"Markdown","content":"You are given a tree $T$ with $N$ vertices. The $i$\\-th edge connects vertices $A_i$ and $B_i$.\nConstruct an $N$\\-vertex rooted tree $R$ that satisfies the following conditions.\n\n*   For all integer pairs $(x,y)$ such that $1 \\leq x < y \\leq N$,\n    *   if the lowest common ancestor in $R$ of vertices $x$ and $y$ is vertex $z$, then vertex $z$ in $T$ is on the simple path between vertices $x$ and $y$.\n*   In $R$, for all vertices $v$ except for the root, the number of vertices of the subtree rooted at $v$, multiplied by $2$, does not exceed the number of vertices of the subtree rooted at the parent of $v$.\n\nWe can prove that such a rooted tree always exists.\n\n## Constraints\n\n*   $1 \\leq N \\leq 10^5$\n*   $1\\leq A_i,B_i \\leq N$\n*   All values in the input are integers.\n*   The given graph is a tree.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$\n$A_1$ $B_1$\n$\\vdots$\n$A_{N-1}$ $B_{N-1}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc291_h","tags":[],"sample_group":[["4\n1 2\n2 3\n3 4","2 -1 4 2\n\nFor example, the lowest common ancestor in $R$ of vertices $1$ and $3$ is vertex $2$; in $T$, vertex $2$ is on the simple path between vertices $1$ and $3$.  \nAlso, for example, in $R$, the subtree rooted at vertex $4$ has two vertices, and the number multiplied by two does not exceed the number of vertices of the subtree rooted at vertex $2$, which has $4$ vertices.\n![image](https://img.atcoder.jp/abc291/7c68a1da41dbfff60a08aad4fe182376.png)"],["5\n1 2\n1 3\n1 4\n1 5","\\-1 1 1 1 1"]],"created_at":"2026-03-03 11:01:14"}}