树上最大值

发布时间: 2018年4月15日 23:14   最后更新: 2018年4月15日 23:25   时间限制: 1000ms   内存限制: 128M

埃森哲信息技术将用您的技术改变世界。利用包括云、人工智能、智能自动化、敏捷开发和开发运维等在内的各项最新数字方法及设计思路,重塑信息技术的明天。运用创新型解决方案,帮助客户在“以数字为先”的当今时代保持领先地位。

  • 通过应用程序管理和服务实施来构建全新的业务模式。
  • 创建并交付定制化的解决方案,为客户解决最为复杂的技术难题。
  • 与全球领先的信息技术服务独立供应商Microsoft, SAP, Oracle, Salesforce, Cisco, HP 及IBM 一起,驱动并促
  • 进业务的真正影响力。
  • 基于我们的应用性研发,让客户体验并尝试使用下一波新兴技术。

说到数字化当然少不了算法,看看下面这种题目你是否能解决

一个连通无向图$G = (V,E)$,共有$n$ 个点,$n-1$ 条边,每个点有一个权值$a[i]$,选取集合$A$ 和集合$B$, $A\cap B = ∅$,使得$A$ 中的点两两形成的路径上的点,和$B$ 中的点两两联通路径上的点没有任何交集

换句话说,定义$A′, \forall u, v \in A$,$u,v$ 简单路径上的点$\in A′$, 定义$B′, \forall u, v 2 \in B$,$u, v$ 简单路径上的点$\in B′$,$ A′ \cap B′ = ∅$。

求A 和B 的” 异或和”之和的最大值,“异或和”是指集合中所包含的点的权值的异或和。

第一行为一个整数$n$ 第二行为$n$ 个整数,表示$a[1] - a[n]$ 接下来$n - 1$ 行每行两个整数,代表$n - 1$ 条边
$1 \le n \le 100000, 1 \le a[i] \le 10^9$

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

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

A∪B 不一定等于 V 。

2018

埃森哲杯第十六届上海大学程序设计联赛春季赛暨上海高校金马五校赛