解题思路
设任选一个点作为根，记从根到点 u 的路径边权异或和为 pre[u]。
那么树上两点 u,v 之间路径的异或和有一个经典结论：
xor(u,v)=pre[u]⊕pre[v]
P4602.第3题-树上异或路径
题目内容
给你一棵有 n 个节点的无向树。每条边有一个非负整数权值 w。请计算这棵树上所有简单路径的异或和之和。注意，本题中树为无向图，端点 (u,v) 与 (v,u) 视为同一路径，仅统计一次。
说明：路径指的是在树上选择两个节点作为端点的简单路径。当两个端点相同的时候，路径长度为 0 ，其异或和为 0 。
【名词解释】
按位异或 (BitwiseXOR)：对两个整数的二进制表示按位进行异或运算。
输入描述
每个测试文件均包含多组测试数据。第一行输入一个整数 T(1≤T≤2×105) 表示数据组数。除此之外，保证单个测试文件的 n 之和不超过 5×105 。每组测试数据的格式如下：
第一行输入一个整数 n(1≤n≤2×105) ，表示节点数量；
此后 n−1 行，每行输入三个整数 u,v,w(1≤u,v≤n;0≤w≤109) 表示一条连接 u 与 v 的边及其权值。保证给出的是一棵树。
输出描述
对于每一组测试数据，新起一行输出一个整数，表示所有简单路径的异或和之和。若结果可能很大，请将答案对 109+7 取模后输出。
样例1
输入
2
3
1 2 1
2 3 2
4
1 2 0
2 3 0
3 4 7
输出
6
21
说明
对于第一组：
-
树为 1−2−3，边权分别为 1,2 ；
-
所有端点对为 {(1,2),(1,3),(2,3)}，对应路径异或和依次为 1,3,2 ；
-
求和得到 1+3+2=6 。
