{"problem":{"name":"F. Dominant Indices","description":{"content":"You are given a rooted undirected tree consisting of $n$ vertices. Vertex $1$ is the root. Let's denote a _depth array_ of vertex $x$ as an infinite sequence $[d_{x, 0}, d_{x, 1}, d_{x, 2}, \\dots]$, ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":4000,"memory_limit":524288},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF1009F"},"statements":[{"statement_type":"Markdown","content":"You are given a rooted undirected tree consisting of $n$ vertices. Vertex $1$ is the root.\n\nLet's denote a _depth array_ of vertex $x$ as an infinite sequence $[d_{x, 0}, d_{x, 1}, d_{x, 2}, \\dots]$, where $d_{x, i}$ is the number of vertices $y$ such that both conditions hold:\n\n*   $x$ is an ancestor of $y$;\n*   the simple path from $x$ to $y$ traverses exactly $i$ edges.\n\nThe _dominant index_ of a _depth array_ of vertex $x$ (or, shortly, the _dominant index_ of vertex $x$) is an index $j$ such that:\n\n*   for every $k < j$, $d_{x, k} < d_{x, j}$;\n*   for every $k > j$, $d_{x, k} \\le d_{x, j}$.\n\nFor every vertex in the tree calculate its _dominant index_.\n\n## Input\n\nThe first line contains one integer $n$ ($1 \\le n \\le 10^6$) — the number of vertices in a tree.\n\nThen $n - 1$ lines follow, each containing two integers $x$ and $y$ ($1 \\le x, y \\le n$, $x \\ne y$). This line denotes an edge of the tree.\n\nIt is guaranteed that these edges form a tree.\n\n## Output\n\nOutput $n$ numbers. $i$\\-th number should be equal to the _dominant index_ of vertex $i$.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"你被给定一棵包含 $n$ 个顶点的有根无向树。顶点 $1$ 为根。\n\n定义顶点 $x$ 的 _深度数组_ 为一个无限序列 $[ d_(x, 0), d_(x, 1), d_(x, 2), dots.h ]$，其中 $d_(x, i)$ 表示满足以下两个条件的顶点 $y$ 的数量：\n\n顶点 $x$ 的 _深度数组_ 的 _主导索引_（简称顶点 $x$ 的 _主导索引_）是指满足以下条件的索引 $j$：\n\n请计算树中每个顶点的 _主导索引_。\n\n第一行包含一个整数 $n$（$1 lt.eq n lt.eq 10^6$）——树中顶点的数量。\n\n接下来 $n - 1$ 行，每行包含两个整数 $x$ 和 $y$（$1 lt.eq x, y lt.eq n$，$x != y$），表示树中的一条边。\n\n保证这些边构成一棵树。\n\n请输出 $n$ 个数。第 $i$ 个数应为顶点 $i$ 的 _主导索引_。\n\n## Input\n\n第一行包含一个整数 $n$（$1 lt.eq n lt.eq 10^6$）——树中顶点的数量。接下来 $n - 1$ 行，每行包含两个整数 $x$ 和 $y$（$1 lt.eq x, y lt.eq n$，$x != y$），表示树中的一条边。保证这些边构成一棵树。\n\n## Output\n\n请输出 $n$ 个数。第 $i$ 个数应为顶点 $i$ 的 _主导索引_。\n\n[samples]","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ T = (V, E) $ be a rooted undirected tree with $ n $ vertices, where $ V = \\{1, 2, \\dots, n\\} $ and vertex $ 1 $ is the root.  \nFor each vertex $ x \\in V $, define the *depth array* $ D_x = (d_{x,0}, d_{x,1}, d_{x,2}, \\dots) $, where:  \n$$\nd_{x,i} = \\left| \\left\\{ y \\in V \\mid \\text{dist}(x, y) = i \\right\\} \\right|\n$$  \nand $ \\text{dist}(x, y) $ denotes the number of edges in the unique path between $ x $ and $ y $ in $ T $.\n\nDefine the *dominant index* of vertex $ x $ as the smallest index $ j \\in \\mathbb{N}_0 $ such that:  \n$$\nd_{x,j} = \\max_{i \\in \\mathbb{N}_0} d_{x,i}\n$$\n\n**Constraints**  \n1. $ 1 \\le n \\le 10^6 $  \n2. The input forms a tree with $ n-1 $ edges.  \n3. For all $ x \\in V $, $ d_{x,i} = 0 $ for all $ i > \\text{diameter}(T) $, so the depth array is effectively finite.\n\n**Objective**  \nFor each vertex $ x \\in \\{1, 2, \\dots, n\\} $, compute its dominant index $ j_x $, i.e., the smallest $ j \\ge 0 $ such that $ d_{x,j} = \\max_{i \\ge 0} d_{x,i} $.  \nOutput the sequence $ (j_1, j_2, \\dots, j_n) $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF1009F","tags":["data structures","dsu","trees"],"sample_group":[["4\n1 2\n2 3\n3 4","0\n0\n0\n0"],["4\n1 2\n1 3\n1 4","1\n0\n0\n0"],["4\n1 2\n2 3\n2 4","2\n1\n0\n0"]],"created_at":"2026-03-03 11:00:39"}}