LuoTianyi and XOR-Tree (Codeforces 1824C)
Tags: Greedy, dsu

LuoTianyi gives you a tree with values in its vertices, and the root of the tree is vertex $$$1$$$.In one operation, you can change the value in one vertex to any non-negative integer.Now you need to find the minimum number of operations you need to perform to make each path from the root to leaf$$$^{\dagger}$$$ has a bitwise XOR value of zero.$$$^{\dagger}$$$A leaf in a rooted tree is a vertex that has exactly one neighbor and is not a root.

Input: The first line contains a single integer $$$n$$$ ($$$2 \le n \le 10^5$$$) — the number of vertices in the tree.The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$), the $$$i$$$-th number represents the value in the $$$i$$$-th vertex.Next $$$n−1$$$ lines describe the edges of the tree. The $$$i$$$-th line contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u_i,v_i \le n, u_i \neq v_i$$$) — the vertices connected by an edge of the tree. It's guaranteed that the given edges form a tree.

Output: Print a single integer — the minimum number of operations.

Note: The tree in the first example:   If we change the value in the vertex $$$2$$$ to $$$3$$$, the value in the vertex $$$5$$$ to $$$4$$$, and the value in the vertex $$$6$$$ to $$$6$$$, then the tree will be ok.The bitwise XOR from the root to the leaf $$$2$$$ will be $$$3 \oplus 3=0$$$.The bitwise XOR from the root to the leaf $$$5$$$ will be $$$4 \oplus 7 \oplus 3=0$$$.The bitwise XOR from the root to the leaf $$$6$$$ will be $$$6 \oplus 5 \oplus 3=0$$$.The tree in the second example:   If we change the value in the vertex $$$2$$$ to $$$4$$$, the value in the vertex $$$3$$$ to $$$27$$$, and the value in the vertex $$$6$$$ to $$$20$$$, then the tree will be ok.The bitwise XOR from the root to the leaf $$$6$$$ will be $$$20 \oplus 19 \oplus 7=0$$$.The bitwise XOR from the root to the leaf $$$8$$$ will be $$$11 \oplus 27 \oplus 4 \oplus 19 \oplus 7=0$$$.The bitwise XOR from the root to the leaf $$$4$$$ will be $$$16 \oplus 4 \oplus 19 \oplus 7=0$$$.The bitwise XOR from the root to the leaf $$$7$$$ will be $$$16 \oplus 4 \oplus 19 \oplus 7=0$$$.In the third example, the only leaf is the vertex $$$4$$$ and the bitwise XOR on the path to it is $$$1 \oplus 2 \oplus 1 \oplus 2 = 0$$$, so we don't need to change values.In the fourth example, we can change the value in the vertex $$$1$$$ to $$$5$$$, and the value in the vertex $$$4$$$ to $$$0$$$.Here $$$\oplus$$$ denotes the bitwise XOR operation.

Sample Inputs:
6
3 5 7 5 8 4
1 2
1 3
1 4
3 5
4 6

8
7 10 7 16 19 9 16 11
1 5
4 2
6 5
5 2
7 2
2 3
3 8

4
1 2 1 2
1 2
2 3
4 3

9
4 3 6 1 5 5 5 2 7
1 2
2 3
4 1
4 5
4 6
4 7
8 1
8 9

Sample Outputs:
3

3

0

2

Solution (Python):
import sys, threading, bisect, math, copy
from heapq import heappush, heappop
from functools import cmp_to_key as ctk, lru_cache
from collections import defaultdict, deque
readline = sys.stdin.readline
read = lambda : list(map(int, readline().split()))
readstr = lambda : readline().rstrip()
alloc = lambda dfv, *s: len(s) != 1 and [alloc(dfv, *s[1:]) for _ in range(int(s[0]))] or [dfv] * int(s[0])
show = lambda arr: print(' '.join(map(str, arr)))

def main():
    INF = float('inf')
    MOD = 10 ** 9 + 7
    dfd = defaultdict(list)
    (n,) = read()
    arr = [0] + read()
    for _ in range(n - 1):
        (a, b) = read()
        dfd[a].append(b)
        dfd[b].append(a)

    def f():
        f = [defaultdict(int) for _ in range(n + 1)]
        cnt = alloc(0, n + 1)
        st = alloc(False, n + 1)
        fa = alloc(0, n + 1)
        dq = deque()
        dq.append(1)
        res = 0
        while dq:
            t = dq[-1]
            if st[t]:
                t = dq.pop()
                mx = 1
                for ne in dfd[t]:
                    if ne == fa[t]:
                        continue
                    if len(f[t]) < len(f[ne]):
                        (f[t], f[ne]) = (f[ne], f[t])
                    for (k, v) in f[ne].items():
                        f[t][k] += v
                        mx = max(mx, f[t][k])
                if cnt[t] == 0:
                    f[t][arr[t]] = 1
                else:
                    res += cnt[t] - mx
                if mx != 1:
                    ndfd = defaultdict(int)
                    for (k, v) in f[t].items():
                        if v == mx:
                            ndfd[k] = 1
                    f[t] = ndfd
                if t == 1:
                    res += int(f[t][0] == 0)
                continue
            st[t] = True
            for ne in dfd[t]:
                if not st[ne]:
                    cnt[t] += 1
                    fa[ne] = t
                    arr[ne] ^= arr[t]
                    dq.append(ne)
        return res
    print(f())
main()

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())
    arr = list(map(int, input().split()))
    neigh = [[] for _ in range(n)]
    for _ in range(n - 1):
        (u, v) = map(int, input().split())
        neigh[u - 1].append(v - 1)
        neigh[v - 1].append(u - 1)
    children = [[] for _ in range(n)]
    parent = [-2] * n
    queue = deque()
    queue.append(0)
    parent[0] = -1
    seq = []
    while queue:
        index = queue.popleft()
        seq.append(index)
        for nextindex in neigh[index]:
            if parent[nextindex] > -2:
                continue
            parent[nextindex] = index
            children[index].append(nextindex)
            queue.append(nextindex)
    dp = [0] * n
    dic = [set() for _ in range(n)]
    lazy = [0] * n
    for index in seq[::-1]:
        if len(children[index]) == 0:
            dic[index].add(arr[index])
            continue
        maxop = 0
        maxlength = 0
        maxindex = -1
        maxfre = 1
        for nextindex in children[index]:
            maxop += dp[nextindex] + 1
            if len(dic[nextindex]) > maxlength:
                maxlength = len(dic[nextindex])
                maxindex = nextindex
        counts = {}
        for nextindex in children[index]:
            if nextindex == maxindex:
                continue
            for key in dic[nextindex]:
                if key ^ lazy[nextindex] not in counts:
                    counts[key ^ lazy[nextindex]] = 0
                counts[key ^ lazy[nextindex]] += 1
                maxfre = max(maxfre, counts[key ^ lazy[nextindex]])
        for key in counts:
            if key ^ lazy[maxindex] in dic[maxindex]:
                counts[key] += 1
                if counts[key] > maxfre:
                    maxfre = counts[key]
        if maxfre > 1:
            for key in counts:
                if counts[key] == maxfre:
                    dic[index].add(key ^ arr[index])
        else:
            dic[index] = dic[maxindex]
            for key in counts:
                dic[index].add(key ^ lazy[maxindex])
            lazy[index] = lazy[maxindex] ^ arr[index]
        dp[index] = maxop - maxfre
    if lazy[0] in dic[0]:
        ans = dp[0]
    else:
        ans = dp[0] + 1
    print(ans)
T = 1
t = 1
while t <= T:
    main(t)
    t += 1

Solution (Python):
import sys
import random
input = sys.stdin.readline
rd = random.randint(10 ** 9, 2 * 10 ** 9)
n = int(input())
a = list(map(int, input().split()))
g = [[] for _ in range(n)]
for _ in range(n - 1):
    (u, v) = map(int, input().split())
    g[u - 1].append(v - 1)
    g[v - 1].append(u - 1)
ans = 0
from types import GeneratorType

def bootstrap(f, stack=[]):

    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to
    return wrappedfunc

@bootstrap
def dfs(son, fa):
    global ans
    if son != 0 and len(g[son]) == 1:
        ans += 1
        yield {a[son]: 1}
    mp = {}
    mx = 0
    for x in g[son]:
        if x != fa:
            a[x] ^= a[son]
            m = (yield dfs(x, son))
            if len(m) > len(mp):
                (mp, m) = (m, mp)
            for (k, v) in m.items():
                mp[k] = mp.get(k, 0) + v
                mx = max(mx, mp[k])
            m.clear()
    if mx > 1:
        ans -= mx - 1
        for k in list(mp.keys()):
            if mp[k] == mx:
                mp[k] = 1
            else:
                del mp[k]
    yield mp
m = dfs(0, -1)
ans -= 0 in m
print(ans)