Dominant Indices (Codeforces 1009F)
Tags: Others, dsu

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.

Input: 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: Output $$$n$$$ numbers. $$$i$$$-th number should be equal to the dominant index of vertex $$$i$$$.


Sample Inputs:
4
1 2
2 3
3 4

4
1 2
1 3
1 4

4
1 2
2 3
2 4

Sample Outputs:
0
0
0
0

1
0
0
0

2
1
0
0

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def bfs(s, u):
    visit = [0] * (n + 1)
    visit[s] = 1
    s0 = [0] * (n + 1)
    t0 = [0] * (n + 1)
    p = [s]
    k = 0
    while k ^ len(p):
        i = p[k]
        (s0[i], t0[i]) = (len(p), len(p))
        for l in range(u[i], u[i + 1]):
            j = G[l]
            if not visit[j]:
                p.append(j)
                visit[j] = 1
                t0[i] += 1
        k += 1
    return (s0, t0, p)

def make_graph(n, m):
    (x, s) = ([], [0] * (n + 3))
    for _ in range(m):
        (u, v) = map(int, input().split())
        s[u + 2] += 1
        s[v + 2] += 1
        x.append(u)
        x.append(v)
    for i in range(3, n + 3):
        s[i] += s[i - 1]
    G = [0] * (2 * m)
    for i in range(2 * m):
        j = x[i] + 1
        G[s[j]] = x[i ^ 1]
        s[j] += 1
    return (G, s)
n = int(input())
(G, u) = make_graph(n, n - 1)
(s, t, p) = bfs(1, u)
d = [[] for _ in range(n + 1)]
ans = [0] * n
for i in p[::-1]:
    (si, ti) = (s[i], t[i])
    if not ti - si:
        d[i].append(1)
        continue
    (ma, k) = (0, 0)
    for c in range(si, ti):
        j = p[c]
        if ma < len(d[j]):
            (ma, k) = (len(d[j]), j)
    ans0 = ans[k - 1] + 1
    dk = d[k]
    ma = dk[-ans0]
    for c in range(si, ti):
        j = p[c]
        if not j ^ k:
            continue
        dj = d[j]
        for l in range(len(dj), 0, -1):
            dk[-l] += dj[-l]
            if ma <= dk[-l]:
                ma = dk[-l]
                ans0 = l
    (d[i], d[k]) = (d[k], d[i])
    d[i].append(1)
    if not ma ^ 1:
        ans0 = 0
    ans[i - 1] = ans0
sys.stdout.write('\n'.join(map(str, ans)))

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def bfs(s):
    visit = [0] * (n + 1)
    visit[s] = 1
    child = [[] for _ in range(n + 1)]
    p = [s]
    k = 0
    while k ^ len(p):
        i = p[k]
        for j in G[i]:
            if not visit[j]:
                p.append(j)
                visit[j] = 1
                child[i].append(j)
        k += 1
    return (child, p)
n = int(input())
G = [[] for _ in range(n + 1)]
for _ in range(n - 1):
    (u, v) = map(int, input().split())
    G[u].append(v)
    G[v].append(u)
(child, p) = bfs(1)
d = [[] for _ in range(n + 1)]
ans = [0] * n
for i in reversed(p):
    if not len(child[i]):
        d[i].append(1)
        continue
    (ma, k) = (0, 0)
    for j in child[i]:
        if ma < len(d[j]):
            (ma, k) = (len(d[j]), j)
    ans0 = ans[k - 1] + 1
    dk = d[k]
    ma = dk[-ans0]
    for j in child[i]:
        if not j ^ k:
            continue
        dj = d[j]
        for l in range(len(dj), 0, -1):
            dk[-l] += dj[-l]
            if ma <= dk[-l]:
                ma = dk[-l]
                ans0 = l
    (d[i], d[k]) = (d[k], d[i])
    d[i].append(1)
    if not ma ^ 1:
        ans0 = 0
    ans[i - 1] = ans0
sys.stdout.write('\n'.join(map(str, ans)))

Solution (Python):
from collections import deque
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def bfs(s):
    q = deque()
    q.append(s)
    visit = [0] * (n + 1)
    visit[s] = 1
    child = [[] for _ in range(n + 1)]
    p = []
    while q:
        i = q.popleft()
        p.append(i)
        for j in G[i]:
            if not visit[j]:
                q.append(j)
                visit[j] = 1
                child[i].append(j)
    return (child, p)
n = int(input())
G = [[] for _ in range(n + 1)]
for _ in range(n - 1):
    (u, v) = map(int, input().split())
    G[u].append(v)
    G[v].append(u)
(child, p) = bfs(1)
d = [[] for _ in range(n + 1)]
ans = [0] * n
while p:
    i = p.pop()
    if not len(child[i]):
        d[i].append(1)
        continue
    (ma, k) = (0, 0)
    for j in child[i]:
        if ma < len(d[j]):
            (ma, k) = (len(d[j]), j)
    ans0 = ans[k - 1] + 1
    dk = d[k]
    ma = dk[-ans0]
    for j in child[i]:
        if not j ^ k:
            continue
        dj = d[j]
        for l in range(len(dj), 0, -1):
            dk[-l] += dj[-l]
            if ma <= dk[-l]:
                ma = dk[-l]
                ans0 = l
    (d[i], d[k]) = (d[k], d[i])
    d[i].append(1)
    if not ma ^ 1:
        ans0 = 0
    ans[i - 1] = ans0
sys.stdout.write('\n'.join(map(str, ans)))