树上的路径非常多, 两点之间的路径有N*N种; 很容易没有头绪
所以遇到要计算树上的路径, 要联想到: (树上的前缀和)操作
即对于两点AB间的路径, 通过(A-根的路径) 和 (B-根的路径) 和 (AB的LCA-根的路径), 进行转换;
而在本题中, AB路径上所有的(边)的异或和 = (A-根的所有边异或和) ^ (B-根的所有边异或和)
可以发现, 连LCA求不用求, 因为(LCA-根的路径), 在异或操作时, 就抵消了;
令Sum(x)为: x到根的(所有边)的异或和, Sum( Root)为0
即两点AB路径的异或和 = Sum( A) ^ Sum( B)
此时问题转换为: 给定N个数, 选择两个数 使得其异或和最大; 这是个模板题
对于一个P进制数, 如果第x位为1, 那么对于所有低位[1,2,3, …, x), 即便全部都取到(P-1), 都不如(第x位取1) 大
… 比如: 10000 大于 09999
因此, 对于一个数A, 二进制为: (b5, b4, b3, b2, b1), b5是高位, 设这里A的(b5)位为0
1, 如果存在一个数, 他的(b5)位, 与 当前数A的(b5)位, 是不同的, 即为1
则, 能与A配对 构成最大的异或和的数, 他的(b5)位, 一定是1
… 即, 我们只需考虑, 所有(b5)位为1的数; (这是贪心策略)
2, 否则, 即所有数的(b5)位 都是0, 那么只考虑所有(b5)位为0的数;
即从高位 往 低位遍历;
上面有个操作是; (只考虑所有(b5)位为1)的数; 这可以通过(Trie)来实现