#2030. 坠梦 | Falling into Dream
坠梦 | Falling into Dream
题目描述
给定一棵 个结点的无根树,每条边有非负整数边权。结点由 编号。
对于每一个点对 ,定义 的距离 为 两点之间唯一简单路径上边权的异或和。
给定两个结点 ,定义点 的价值 为 与 的距离的异或和,即
$$\operatorname{val}_{x, y}(i) = \operatorname{dis}(x, i) \oplus \operatorname{dis}(y, i) \textsf{。}$$现在有 次询问,每次询问给出四个整数 ,求 $\displaystyle \bigoplus_{i = l}^{r} \operatorname{val}_{x, y}(i)$ 的值,即求
$$\operatorname{val}_{x, y}(l) \oplus \operatorname{val}_{x, y}(l + 1) \oplus \cdots \oplus \operatorname{val}_{x, y}(r - 1) \oplus \operatorname{val}_{x, y}(r) \textsf{。}$$上述公式中, 表示二进制按位异或。
输入格式
第一行,两个整数 。
接下来 行,每行三个整数 ,表示 之间有一条权值为 的边。
接下来 行,每行四个整数 ,表示一次询问。
输出格式
输出 行,每行一个整数,为每次询问的答案。
样例
3 2
1 2 1
2 3 1
1 2 1 3
2 3 2 3
1
0
题目来源:洛谷 P8965