原题链接

思路

预处理各节点到根（如节点 1）的异或值，转化为数组中两数异或最大值问题。使用字典树逐位确定最大异或结果。

std

class TrieNode:
    def __init__(self):
        self.children = [None, None]

def insert(root, num):
    node = root
    for i in range(31, -1, -1):
        bit = (num >> i) & 1
        if not node.children[bit]:
            node.children[bit] = TrieNode()
        node = node.children[bit]

def query(root, num):
    node = root
    max_xor = 0
    for i in range(31, -1, -1):
        bit = (num >> i) & 1
        toggle = 1 - bit
        if node.children[toggle]:
            max_xor |= (1 << i)
            node = node.children[toggle]
        else:
            node = node.children[bit] or node
    return max_xor

n = int(input())
w = list(map(int, input().split()))
from collections import defaultdict
tree = defaultdict(list)
for _ in range(n-1):
    u, v = map(int, input().split())
    tree[u].append(v)
    tree[v].append(u)

xor = [0]*(n+1)
visited = [False]*(n+1)
stack = [(1, 0)]
while stack:
    u, val = stack.pop()
    if visited[u]:
        continue
    visited[u] = True
    xor[u] = val ^ w[u-1]
    for v in tree[u]:
        if not visited[v]:
            stack.append((v, xor[u]))

root = TrieNode()
max_val = 0
for num in xor[1:]:
    insert(root, num)
    max_val = max(max_val, query(root, num))
print(max_val)

【AI 提供】数据生成代码

import random
n = 10**5
print(n)
w = [random.randint(0, 2**31-1) for _ in range(n)]
print(' '.join(map(str, w)))
# 生成树结构
parent = list(range(n+1))
edges = []
for i in range(2, n+1):
    p = random.randint(1, i-1)
    edges.append((p, i))
random.shuffle(edges)
for u, v in edges[:n-1]:
    print(u, v)

【实际上】数据生成代码

import random
from collections import defaultdict

class TrieNode:
    def __init__(self):
        self.children = [None, None]

def insert(root, num):
    node = root
    for i in range(31, -1, -1):
        bit = (num >> i) & 1
        if not node.children[bit]:
            node.children[bit] = TrieNode()
        node = node.children[bit]

def query(root, num):
    node = root
    max_xor = 0
    for i in range(31, -1, -1):
        bit = (num >> i) & 1
        toggle = 1 - bit
        if node.children[toggle]:
            max_xor |= (1 << i)
            node = node.children[toggle]
        else:
            node = node.children[bit] or node
    return max_xor

for case in range(1, 11):
    n = random.randint(1, 10**5)
    w = [random.randint(0, 2**31-1) for _ in range(n)]
    # 生成树结构
    parent = list(range(n+1))
    edges = []
    for i in range(2, n+1):
        p = random.randint(1, i-1)
        edges.append((p, i))
    random.shuffle(edges)
    with open(f'c{case}.in', 'w') as f:
        print(n, file=f)
        print(' '.join(map(str, w)), file=f)
        for u, v in edges[:n-1]:
            print(u, v, file=f)
    with open(f'c{case}.out', 'w') as f:
        tree = defaultdict(list)
        for u, v in edges:
            tree[u].append(v)
            tree[v].append(u)
        xor = [0]*(n+1)
        visited = [False]*(n+1)
        stack = [(1, 0)]
        while stack:
            u, val = stack.pop()
            if visited[u]:
                continue
            visited[u] = True
            xor[u] = val ^ w[u-1]
            for v in tree[u]:
                if not visited[v]:
                    stack.append((v, xor[u]))
        root = TrieNode()
        max_val = 0
        for num in xor[1:]:
            insert(root, num)
            max_val = max(max_val, query(root, num))
        print(max_val, file=f)

加载中... 加载中...