There Should Be a Lot of Maximums (Codeforces 1805E)
Tags: DP, trees

You are given a tree (a connected graph without cycles). Each vertex of the tree contains an integer. Let's define the $$$\mathrm{MAD}$$$ (maximum double) parameter of the tree as the maximum integer that occurs in the vertices of the tree at least $$$2$$$ times. If no number occurs in the tree more than once, then we assume $$$\mathrm{MAD}=0$$$.Note that if you remove an edge from the tree, it splits into two trees. Let's compute the $$$\mathrm{MAD}$$$ parameters of the two trees and take the maximum of the two values. Let the result be the value of the deleted edge.For each edge, find its value. Note that we don't actually delete any edges from the tree, the values are to be found independently.

Input: The first line contains one integer $$$n$$$ ($$$2 \le n \le 10^5$$$) — the number of vertices in the tree.Each of the next $$$n - 1$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$) — the ends of an edge of the tree. It's guaranteed that the given edges form a valid tree.The last line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the numbers in the vertices.

Output: For each edge in the input order, print one number — the maximum of the $$$\mathrm{MAD}$$$ parameters of the two trees obtained after removing the given edge from the initial tree.

Note:   In the first example, after removing edge $$$(1, 2)$$$ no number repeats $$$2$$$ times in any of the resulting subtrees, so the answer is $$$\max(0, 0)=0$$$.After removing edge $$$(2, 3)$$$, in the bigger subtree, $$$1$$$ is repeated twice, and $$$2$$$ is repeated twice, so the $$$\mathrm{MAD}$$$ of this tree is $$$2$$$.After removing edge $$$(2, 4)$$$, in the bigger subtree, only the number $$$1$$$ is repeated, and in the second subtree, only one number appears, so the answer is $$$1$$$.In the second example, if edge $$$1 \leftrightarrow 4$$$ is not removed, then one of the subtrees will have two $$$1$$$, so the answer — $$$1$$$. And if edge $$$1 \leftrightarrow 4$$$ is deleted, both subtrees have no repeating values, so the answer is $$$0$$$.

Sample Inputs:
5
1 2
2 3
2 4
1 5
2 1 3 2 1

6
1 2
1 3
1 4
4 5
4 6
1 2 3 1 4 5

Sample Outputs:
0
2
1
2

1
1
0
1
1

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

def make_graph(n, m):
    (x, s) = ([0] * (2 * m), [0] * (n + 3))
    for i in range(0, 2 * m, 2):
        (u, v) = map(int, input().split())
        s[u + 2] += 1
        s[v + 2] += 1
        (x[i], x[i + 1]) = (u, 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, x)

def bfs(s):
    q = [s]
    visit = [0] * (n + 1)
    visit[s] = 1
    parent = [-1] * (n + 1)
    for k in range(n):
        i = q[k]
        for v in range(s0[i], s0[i + 1]):
            j = G[v]
            if not visit[j]:
                q.append(j)
                visit[j] = 1
                parent[j] = i
    return parent
n = int(input())
(G, s0, x) = make_graph(n, n - 1)
e = dict()
for i in range(n - 1):
    (u, v) = (x[2 * i], x[2 * i + 1])
    (e[u, v], e[v, u]) = (i, i)
a = [0] + list(map(int, input().split()))
r0 = random.randint(1, pow(2, 30) - 1)
d = defaultdict(lambda : [])
for i in range(1, n + 1):
    d[a[i] ^ r0].append(i)
ans = [0] * (n - 1)
y = list(set(sorted(a[1:])))
y.sort(reverse=True)
y = [i ^ r0 for i in y]
f = 0
for i in y:
    if len(d[i]) >= 3:
        f = 1
        ans = [i ^ r0] * (n - 1)
        break
    elif len(d[i]) == 2:
        f = 1
        parent = bfs(d[i][0])
        u = [d[i][1]]
        while u[-1] ^ d[i][0]:
            u.append(parent[u[-1]])
        break
if f and ans[0] or not f:
    sys.stdout.write('\n'.join(map(str, ans)))
    exit()
c = [-1] * (n + 1)
l0 = len(u)
for i in range(l0):
    c[u[i]] = i
q = list(u)
for k in range(n):
    i = q[k]
    for v in range(s0[i], s0[i + 1]):
        j = G[v]
        if c[j] == -1:
            q.append(j)
            c[j] = c[i]
a0 = a[u[0]]
ans = [a0] * (n - 1)
for i in range(l0 - 1):
    ans[e[u[i], u[i + 1]]] = 0
(l, r) = (0, l0 - 1)
for i in y:
    if i ^ r0 >= a0:
        continue
    if len(d[i]) >= 3:
        ans = [max(i ^ r0, j) for j in ans]
        break
    elif len(d[i]) == 1:
        continue
    (l1, r1) = (c[d[i][0]], c[d[i][1]])
    if l1 > r1:
        (l1, r1) = (r1, l1)
    while l < l1 and l < r:
        ans[e[u[l], u[l + 1]]] = i ^ r0
        l += 1
    while r > r1 and l < r:
        ans[e[u[r], u[r - 1]]] = i ^ r0
        r -= 1
sys.stdout.write('\n'.join(map(str, ans)))

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

def main(t):
    n = int(input())
    neigh = [[] for _ in range(n)]
    edges = {}
    for i in range(n - 1):
        (u, v) = map(int, input().split())
        neigh[u - 1].append(v - 1)
        neigh[v - 1].append(u - 1)
        edges[min(u, v) - 1, max(u, v) - 1] = i
    arr = list(map(int, input().split()))
    valid = []
    fre = {}
    for num in arr:
        if str(num) not in fre:
            fre[str(num)] = 0
        fre[str(num)] += 1
    maxtriple = 0
    for key in fre:
        if fre[key] == 2:
            valid.append(int(key))
        if fre[key] > 2:
            maxtriple = max(maxtriple, int(key))
    valid.sort(reverse=True)
    while valid and valid[-1] < maxtriple:
        valid.pop()
    if len(valid) == 0:
        for _ in range(n - 1):
            print(maxtriple)
        return
    k = len(valid)
    represent = {}
    for i in range(len(valid)):
        represent[valid[i]] = i
    root = 0
    while arr[root] != valid[0]:
        root += 1
    alter = root + 1
    while arr[alter] != valid[0]:
        alter += 1
    valid.append(maxtriple)
    queue = deque()
    queue.append(root)
    children = [[] for _ in range(n)]
    parent = [-2] * n
    parent[root] = -1
    while queue:
        index = queue.popleft()
        for nextindex in neigh[index]:
            if parent[nextindex] > -2:
                continue
            parent[nextindex] = index
            children[index].append(nextindex)
            queue.append(nextindex)
    path = [alter]
    while path[-1] != root:
        path.append(parent[path[-1]])
    m = len(path)
    gift = [set() for _ in range(m)]
    for i in range(m - 1):
        index = path[i]
        if i > 0:
            son = path[i - 1]
        else:
            son = -1
        queue.append(index)
        while queue:
            j = queue.popleft()
            if arr[j] in represent:
                num = represent[arr[j]]
                if num in gift[i]:
                    gift[i].remove(num)
                else:
                    gift[i].add(num)
            for nextj in children[j]:
                if nextj == son:
                    continue
                queue.append(nextj)
    ans = [-1] * (n - 1)
    curr = [0] * (k + 1)
    mex = 0
    for i in range(m - 1):
        for num in gift[i]:
            curr[num] ^= 1
            if curr[num] == 0 and num < mex:
                mex = num
        while curr[mex] == 1:
            mex += 1
        (u, v) = (min(path[i], parent[path[i]]), max(path[i], parent[path[i]]))
        ans[edges[u, v]] = valid[mex]
    for i in range(n - 1):
        if ans[i] < 0:
            ans[i] = valid[0]
    for num in ans:
        print(num)
T = 1
t = 1
while t <= T:
    main(t)
    t += 1

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

def make_graph(n, m):
    (x, s) = ([0] * (2 * m), [0] * (n + 3))
    for i in range(0, 2 * m, 2):
        (u, v) = map(int, input().split())
        s[u + 2] += 1
        s[v + 2] += 1
        (x[i], x[i + 1]) = (u, 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, x)

def bfs(s):
    q = [s]
    visit = [0] * (n + 1)
    visit[s] = 1
    parent = [-1] * (n + 1)
    for k in range(n):
        i = q[k]
        for v in range(s0[i], s0[i + 1]):
            j = G[v]
            if not visit[j]:
                q.append(j)
                visit[j] = 1
                parent[j] = i
    return parent
n = int(input())
(G, s0, x) = make_graph(n, n - 1)
e = dict()
for i in range(n - 1):
    (u, v) = (x[2 * i], x[2 * i + 1])
    (e[u, v], e[v, u]) = (i, i)
a = [0] + list(map(int, input().split()))
r0 = random.randint(1, pow(2, 30) - 1)
d = defaultdict(lambda : [])
for i in range(1, n + 1):
    d[a[i] ^ r0].append(i)
ans = [0] * (n - 1)
y = list(set(sorted(a[1:])))
y.sort(reverse=True)
y = [i ^ r0 for i in y]
f = 0
for i in y:
    if len(d[i]) >= 3:
        f = 1
        ans = [i ^ r0] * (n - 1)
        break
    elif len(d[i]) == 2:
        f = 1
        parent = bfs(d[i][0])
        u = [d[i][1]]
        while u[-1] ^ d[i][0]:
            u.append(parent[u[-1]])
        break
if f and ans[0] or not f:
    sys.stdout.write('\n'.join(map(str, ans)))
    exit()
c = [-1] * (n + 1)
l0 = len(u)
for i in range(l0):
    c[u[i]] = i
q = list(u)
for k in range(n):
    i = q[k]
    for v in range(s0[i], s0[i + 1]):
        j = G[v]
        if c[j] == -1:
            q.append(j)
            c[j] = c[i]
a0 = a[u[0]]
ans = [a0] * (n - 1)
for i in range(l0 - 1):
    ans[e[u[i], u[i + 1]]] = 0
(l, r) = (0, l0 - 1)
for i in y:
    if i ^ r0 >= a0:
        continue
    if len(d[i]) >= 3:
        ans = [max(i ^ r0, j) for j in ans]
        break
    elif len(d[i]) == 1:
        continue
    (l1, r1) = (c[d[i][0]], c[d[i][1]])
    if l1 > r1:
        (l1, r1) = (r1, l1)
    while l < l1 and l < r:
        ans[e[u[l], u[l + 1]]] = i ^ r0
        l += 1
    while r > r1 and l < r:
        ans[e[u[r], u[r - 1]]] = i ^ r0
        r -= 1
sys.stdout.write('\n'.join(map(str, ans)))