F. Dominant Indices
data structures; dsu; trees
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]\), where \(d_{x, i}\) is the number of vertices \(y\) such that both conditions hold: \(x\) is an ancestor of \(y\); the simple path from \(x\) to \(y\) traverses exactly \(i\) edges. The dominant index of a depth array of vertex \(x\) (or, shortly, the dominant index of vertex \(x\)) is an index \(j\) such that: for every \(k < j\), \(d_{x, k} < d_{x, j}\); for every \(k > j\), \(d_{x, k} \le d_{x, j}\). For every vertex in the tree calculate its dominant index.
The first line contains one integer \(n\) (\(1 \le n \le 10^6\)) — the number of vertices in a tree.Then \(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.It is guaranteed that these edges form a tree.
Output \(n\) numbers. \(i\)-th number should be equal to the dominant index of vertex \(i\).