树上最大值
题号:NC15612
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 128 M,其他语言256 M
64bit IO Format: %lld

题目描述

埃森哲信息技术将用您的技术改变世界。利用包括云、人工智能、智能自动化、敏捷开发和开发运维等在 内的各项最新数字方法及设计思路,重塑信息技术的明天。运用创新型解决方案,帮助客户在“以数字为先” 的当今时代保持领先地位。
 • 通过应用程序管理和服务实施来构建全新的业务模式。
 • 创建并交付定制化的解决方案,为客户解决最为复杂的技术难题。
 • 与全球领先的信息技术服务独立供应商 Microsoft, SAP, Oracle, Salesforce, Cisco, HP 及 IBM 一起,驱 动并促进业务的真正影响力。
 • 基于我们的应用性研发,让客户体验并尝试使用下一波新兴技术。 说到数字化当然少不了算法,看看下面这种题目你是否能解决 

一个连通无向图 G = (V, E),共有 n 个点,n − 1 条边,每个点有一个权值 a[i],选取集合 A 和集合 B, A ∩ B = ∅,
使得 A 中的点两两形成的路径上的点,和 B 中的点两两联通路径上的点没有任何交集。换句话说,定义 A′ ,∀u, v ∈ A,u, v 简单路径上的点 ∈ A′ , 定义 B′ ,∀u, v ∈ B,u, v 简单路径上的点 ∈ B′ , A′ ∩ B′ = ∅。
 求 A 和 B 的” 异或和”之和的最大值,“异或和”是指集合中所包含的点的权值的异或和。

输入描述:

第一行为一个整数 n 第二行为 n 个整数,表示 a[1] ∼ a[n] 接下来 n − 1 行每行两个整数,代表 n − 1 条边。1 ≤ n ≤ 100000 1 ≤ a[i] ≤ 10

输出描述:

一个整数,表示两个集合的“异或和”之和。
示例1

输入

复制
7
8 4 4 2 1 2 1
1 2
2 4
2 5
3 1
3 6
3 7

输出

复制
22

备注:

A∪B 不一定等于 V 。