#P2420. 让我们异或吧

    ID: 1428 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>树形结构洛谷原创深度优先搜索DFS最近公共祖先LCA树链剖分树剖

让我们异或吧

题目描述

异或是一种神奇的运算,大部分人把它总结成不进位加法.

在生活中 xor 运算也很常见。比如,对于一个问题的回答,是为 11,否为 00,那么:

AA 是否是男生)xor(BB 是否是男生)= AABB 是否能够成为情侣

好了,现在我们来制造和处理一些复杂的情况。比如我们将给出一颗树,它很高兴自己有 NN 个结点。树的每条边上有一个权值。我们要进行 MM 次询问,对于每次询问,我们想知道某两点之间的路径上所有边权的异或值。

输入格式

输入文件第一行包含一个整数 NN ,表示这颗开心的树拥有的结点数,以下有 N1N-1 行,描述这些边,每行有3个数,u,v,wu,v,w,表示 uuvv 之间有一条权值为 ww 的边。接下来一行有一个整数 MM,表示询问数。之后的 MM 行,每行两个数 u,vu,v,表示询问这两个点之间的路径上的权值异或值。

输出格式

输出 MM 行,每行一个整数,表示异或值

5
1 4 9644
2 5 15004
3 1 14635
5 3 9684
3
2 4
5 4
1 1

975
14675
0

提示

对于 40%40\% 的数据,有 1N,M30001 \le N,M \le 3000
对于 100%100\% 的数据,有 1N,M1000001 \le N ,M\le 100000

保证边权在 int 范围内。