首页 > 代码库 > [bzoj 1954]Pku3764 The xor-longest Path
[bzoj 1954]Pku3764 The xor-longest Path
传送门 :http://www.lydsy.com/JudgeOnline/problem.php?id=1954
Pku3764 The xor-longest Path
Time Limit: 1 Sec Memory Limit: 64 MBSubmit: 839 Solved: 369
[Submit][Status][Discuss]
Description
给定一棵n个点的带权树，求树上最长的异或和路径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
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....
对于x，y之间的异或和，等于x到根节点的异或和 ^ y到根节点的异或和。
然后把它们丢到trie里，贪心就好。
代码待补
[bzoj 1954]Pku3764 The xor-longest Path
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。