【问题描述】

求一颗带边权的树的一条最大Xor路径的值。

【输入格式】

第一行,一个整数N,表示一颗树有N个节点,接下来N-1行,每行三个整数a b c表示节点a和节点b之间有条权值为c的边。

【输出格式】

输出仅一行,即所求的最大值。

【输入样例】

4

1 2 3

1 3 4

1 4 7

【输出样例】

7

【数据范围】

对于100%的数据:1≤N≤100000,c≤2^31-1

Xor有一个重要的性质就是a xor b xor b=a 于是树上两点的情况就等于他们到根节点的xor值的xor值(LCA以上部分互相抵消)于是我们可以将xor值转化为一个二进制数,从高位到低位存进Trie树里,每次把前缀丢进Trie里查找,如果是1就尽可能到这一位是0的结点去,是0就到1的结点去(如果存在),BFS一遍就能得到最大值。

下面是代码:

 

本文为原创文章,唯一地址链接:【Xor】 转载请注明转自 stdKonjac

我来吐槽

*

*

取消

*