LuoTianyi and XOR-Tree (Codeforces 1825E)
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 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 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 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