首页 > 其他 > 详细

[bzoj 1954]Pku3764 The xor-longest Path

时间：2017-05-29 10:48:14 阅读：285 评论：0 收藏：0 [点我收藏+]

传送门 :http://www.lydsy.com/JudgeOnline/problem.php?id=1954

Pku3764 The xor-longest Path

Time Limit: 1 Sec Memory Limit: 64 MB
Submit: 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

Sample Output

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

原文：http://www.cnblogs.com/kvrmnks/p/6917317.html

踩

(0)

评论一句话评论（0）

分享档案

更多>

2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)