stdKonjac's Blog

An AC a day keeps the WA away ~

【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一遍就能得到最大值。

下面是代码:

 

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注

*

This site uses Akismet to reduce spam. Learn how your comment data is processed.