【Xor】

【问题描述】

求一颗带边权的树的一条最大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一遍就能得到最大值。

下面是代码:

 

stdKonjac

stdKonjac

一只挣扎的蒟蒻ACMer

评论太激烈有些评论需要亲动动手指翻页

留下你的评论

*评论支持代码高亮<pre class="prettyprint linenums">代码</pre>

*