Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom1年前

06/6
10:33
trie

[bzoj 1954] Pku3764 The xor-longest Path

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

 1954
给定一棵n个点的带权树,求树上最长的异或和路径
(1)

♦♦♦♦♦♦   Input   ♦♦♦♦♦♦

The input contains several test cases. The first line of each test case contains an integer n(1<=n<=100000), The following n-1 lines each contains three integers u(0 <= u < n),v(0 <= v < n),w(0 <= w < 2^31), which means there is an edge between node u and v of length w.

♦♦♦♦♦♦   Output   ♦♦♦♦♦♦

For each test case output the xor-length of the xor-longest path.

♦♦♦♦♦♦   Sample Input   ♦♦♦♦♦♦

4
1 2 3
2 3 4
2 4 6

♦♦♦♦♦♦   Sample Output   ♦♦♦♦♦♦

7

♦♦♦♦♦♦   Hint   ♦♦♦♦♦♦

The xor-longest path is 1->2->3, which has length 7 (=3 ⊕ 4)
注意:结点下标从1开始到N....

♦♦♦♦♦♦   题解  ♦♦♦♦♦♦

先求出从根到每个点的路径异或和,然后问题就变成了选两个点使它们的异或值最大,trie的经典运用。先把每个数插入到trie上,然后查询的时候尽量走不一样的...

 

[bzoj 1954] Pku3764 The xor-longest Path