Processing math: 100%
编程题
                ### 问题描述

小明有一颗树,这棵树拥有 n 个结点和 n1 条边,这 n1 条边都有自己的权值 v。当小明盯着这棵树看的时候,他突然想到了一个问题:如果两个结点之间的距离被定义为它们之间的唯一简单路径上各条边权值的异或和,那么在 q 次询问中,每次给出一对结点 xy,代表小明想要了解它们之间的距离,即它们之间的唯一简单路径上各条边权值的异或和。小明希望你能够快速解答这些询问。你能帮助他解决这个问题吗?

输入格式

第一行,包含一个正整数 n (1n105) ,代表这棵拥有 n 个结点。

接下来 n1 行,每行的输入格式如下:

  • l r v (1l,rn)(1v109) ,代表结点 lr 之间有一条权值为 v 的边。

接下来一行,包含一个正整数 q (1q105) ,代表小明将要进行 q 次询问。

接下来 q 行,每行输入格式如下:

  • x y (1x,yn) ,代表小明询问 xy 之间的距离。

输出格式

对于每次询问,共 q 行,每行包含一个正整数,代表 xy 之间的距离。

输入样例

4
1 2 4
2 3 3
3 4 2
3
4 3
3 1
1 1

输出样例

2
7
0

样例说明

样例中,对于第一次询问,小明询问 43 之间的距离,即为 2 ,故输出 2

对于第二次询问,小明询问 31 之间的距离,即为 43=7 ,故输出 7

对于第三次询问,小明询问 11 之间的距离,为 0 ,故输出 0

查看答案
赣ICP备20007335号-2