XOR Tree (Codeforces 1709E)
Tags: Greedy, dsu

You are given a tree consisting of $$$n$$$ vertices. A number is written on each vertex; the number on vertex $$$i$$$ is equal to $$$a_i$$$.Recall that a simple path is a path that visits each vertex at most once. Let the weight of the path be the bitwise XOR of the values written on vertices it consists of. Let's say that a tree is good if no simple path has weight $$$0$$$.You can apply the following operation any number of times (possibly, zero): select a vertex of the tree and replace the value written on it with an arbitrary positive integer. What is the minimum number of times you have to apply this operation in order to make the tree good?

Input: The first line contains one integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of vertices.The second line contains $$$n$$$ integers $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$1 \le a_i < 2^{30}$$$) — the numbers written on vertices.Then $$$n - 1$$$ lines follow, each containing two integers $$$x$$$ and $$$y$$$ ($$$1 \le x, y \le n; x \ne y$$$) denoting an edge connecting vertex $$$x$$$ with vertex $$$y$$$. It is guaranteed that these edges form a tree.

Output: Print a single integer — the minimum number of times you have to apply the operation in order to make the tree good.

Note: In the first example, it is enough to replace the value on the vertex $$$1$$$ with $$$13$$$, and the value on the vertex $$$4$$$ with $$$42$$$.

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

4
2 1 1 1
1 2
1 3
1 4

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

Sample Outputs:
2

0

2

Solution (Python):
from collections import defaultdict
import sys, threading
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(10 ** 6)
threading.stack_size(2 ** 27)

def main():
    N = int(input())
    A = [int(x) for x in input().split()]
    G = [[] for _ in range(N)]
    for _ in range(N - 1):
        (x, y) = [int(x) - 1 for x in input().split()]
        G[x].append(y)
        G[y].append(x)
    B = [0] * N
    vals = defaultdict(set)
    res = [0]

    def fill_dfs(v, p):
        B[v] = A[v]
        if p != -1:
            B[v] ^= B[p]
        for u in G[v]:
            if u != p:
                fill_dfs(u, v)

    def calc_dfs(v, p):
        zero = False
        vals[v].add(B[v])
        for u in G[v]:
            if u != p:
                calc_dfs(u, v)
                if len(vals[v]) < len(vals[u]):
                    (vals[v], vals[u]) = (vals[u], vals[v])
                for x in vals[u]:
                    zero |= x ^ A[v] in vals[v]
                for x in vals[u]:
                    vals[v].add(x)
                vals[u].clear()
        if zero:
            res[0] += 1
            vals[v].clear()
    fill_dfs(0, -1)
    calc_dfs(0, -1)
    print(res[0])
threading.Thread(target=main).start()

Solution (Python):
from __future__ import print_function
from math import *
from collections import defaultdict, deque
import os
import random
import sys
from io import BytesIO, IOBase
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

def main():
    pass
BUFSIZE = 8192

def lcm(a, b):
    return a * b // gcd(a, b)

def ceilDiv(a, b):
    if a % b == 0:
        return a // b
    else:
        return a // b + 1

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')

class myDict:

    def __init__(self, func):
        self.RANDOM = random.randint(0, 1 << 32)
        self.default = func
        self.dict = {}

    def __getitem__(self, key):
        myKey = self.RANDOM ^ key
        if myKey not in self.dict:
            self.dict[myKey] = self.default()
        return self.dict[myKey]

    def __setitem__(self, key, item):
        myKey = self.RANDOM ^ key
        self.dict[myKey] = item

    def __contains__(self, key):
        return key ^ self.RANDOM in self.dict

    def getKeys(self):
        return [self.RANDOM ^ i for i in self.dict]
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
mod = 10 ** 9 + 7

def inp():
    return int(input())

def inlt():
    return list(map(int, input().split()))

def insr():
    s = input()
    return list(s[:len(s)])

def invr():
    return map(int, input().split())

@bootstrap
def dfs(node, parent):
    global curxor, ans
    curxor ^= val[node]
    maxnum = 0
    maxchild = -1
    f = 0
    for child in l[node]:
        if child != parent:
            yield dfs(child, node)
            if maxnum < num[child]:
                if maxchild != -1:
                    maxnum = num[child]
                    (maxchild, child) = (child, maxchild)
                    for j in d[child]:
                        if j ^ val[node] in d[maxchild]:
                            f = 1
                            break
                    for j in d[child]:
                        d[maxchild].add(j)
                    d[child].clear()
                    maxnum = len(d[maxchild])
                else:
                    maxnum = num[child]
                    maxchild = child
            if maxchild != -1 and maxchild != child:
                for j in d[child]:
                    if j ^ val[node] in d[maxchild]:
                        f = 1
                        break
                for j in d[child]:
                    d[maxchild].add(j)
                d[child].clear()
                maxnum = len(d[maxchild])
    if maxchild != -1:
        if val[node] ^ curxor in d[maxchild]:
            f = 1
    if f:
        ans += 1
    else:
        if maxchild != -1:
            d[node] = d[maxchild]
        d[node].add(curxor)
    num[node] = len(d[node])
    curxor ^= val[node]
    yield None
n = inp()
val = inlt()
l = [[] for i in range(n)]
for i in range(n - 1):
    (a, b) = invr()
    l[a - 1].append(b - 1)
    l[b - 1].append(a - 1)
d = [set() for i in range(n)]
num = [0 for i in range(n)]
curxor = 0
ans = 0
dfs(0, -1)
print(ans)

Solution (Python):
import sys
import io
import os
BUFSIZE = 8192

class FastIO(io.IOBase):
    newlines = 0

    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.buffer = io.BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(io.IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
    """"""
    (sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop('end', '\n'))
    if kwargs.pop('flush', False):
        file.flush()
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def input():
    return sys.stdin.readline().rstrip('\r\n')

def read_int_list():
    return list(map(int, input().split()))

def read_int_tuple():
    return tuple(map(int, input().split()))

def read_int():
    return int(input())
from types import GeneratorType

def bootstrap(f, stack=[]):

    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        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

def main():
    n = read_int()
    a = read_int_list()
    tree = [[] for _ in range(n)]
    for _ in range(n - 1):
        (u, v) = read_int_tuple()
        tree[u - 1].append(v - 1)
        tree[v - 1].append(u - 1)

    @bootstrap
    def dfs(u, p=-1, cur=0):
        cur ^= a[u]
        (flag, cur_set) = (True, {cur})
        for v in tree[u]:
            if v == p:
                continue
            son_set = (yield dfs(v, u, cur))
            if len(son_set) > len(cur_set):
                (son_set, cur_set) = (cur_set, son_set)
            flag &= not any((x ^ a[u] in cur_set for x in son_set))
            cur_set |= son_set
        if not flag:
            nonlocal res
            res += 1
            cur_set.clear()
        yield cur_set
    res = 0
    dfs(0)
    print(res)
main()