#2030. 坠梦 | Falling into Dream

坠梦 | Falling into Dream

题目描述

给定一棵 nn 个结点的无根树,每条边有非负整数边权。结点由 1∼n1 \sim n 编号。

对于每一个点对 (x,y)(x, y),定义 (x,y)(x, y) 的距离 dis⁡(x,y)\operatorname{dis}(x, y) 为 x,yx,y 两点之间唯一简单路径上边权的异或和。

给定两个结点 x,yx, y,定义点 ii 的价值 val⁡x,y(i)\operatorname{val}_{x, y}(i) 为 (x,i)(x, i) 与 (y,i)(y, i) 的距离的异或和,即

$$\operatorname{val}_{x, y}(i) = \operatorname{dis}(x, i) \oplus \operatorname{dis}(y, i) \textsf{。}$$

现在有 qq 次询问,每次询问给出四个整数 x,y,l,rx, y, l, r,求 $\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{。}$$

上述公式中,⊕\oplus 表示二进制按位异或。

输入格式

第一行,两个整数 n,qn, q。

接下来 n−1n - 1 行,每行三个整数 u,v,wu, v, w,表示 u,vu, v 之间有一条权值为 ww 的边。

接下来 qq 行,每行四个整数 x,y,l,rx,y,l,r,表示一次询问。

输出格式

输出 qq 行,每行一个整数,为每次询问的答案。

样例

3 2
1 2 1
2 3 1
1 2 1 3
2 3 2 3
1
0

题目来源:洛谷 P8965