P6071 『MdOI R1』Treequery

给定一棵 $n$ 个点的无根树，边有边权。 令 $E(x,y)$ 表示树上 $x,y$ 之间的简单路径上的所有边的集合，特别地，当 $x=y$ 时，$E(x,y) = \varnothing$。 你需要 **实时** 回答 $q$ 个询问，每个询问给定 $p,l,r$，请你求出集合 $\bigcap_{i=l}^r E(p,i)$ 中所有边的边权和，即 $E(p, l\dots r)$ 的交所包含的边的边权和。 通俗的讲，你需要求出 $p$ 到 $[l,r]$ 内每一个点的简单路径的公共部分长度。

无

无

【样例 1 说明】 样例中的树如图所示：  下面解释中的询问参数均为异或 $lastans$ 之后得到的真实值。 对于第一个询问，$p=2$，$l=3$，$r=5$，$\bigcap_{i=3}^5 E(2,i)$ 为边 $(2,3)$，长度为 $3$。 对于第二个询问，$p=1$，$l=2$，$r=4$，$\bigcap_{i=2}^4 E(1,i)$ 为边 $(1,3)$，长度为 $2$； 对于第三个询问，$p=2$，$l=5$，$r=5$，$\bigcap_{i=5}^5 E(2,i)$ 为边集 $\{(2,3),(3,1),(1,5)\}$，长度为 $6$； 对于第四个询问，$p=3$，$l=3$，$r=4$，$\bigcap_{i=3}^4 E(3,i)=\varnothing$，长度为 $0$。 --- 【数据范围】 **本题采用捆绑测试。** | 子任务编号 | $n,q\leq$ | 特殊性质 | 分值 | | :--------: | :------------: | :------: | :--: | | 1 | $10^5$ | $l=r$ | 8 | | 2 | $10^5$ | $p=1$ | 20 | | 3 | $10^3$ | 无 | 20 | | 4 | $10^5$ | 无 | 26 | | 5 | $2\times 10^5$ | 无 | 26 | 对于 $100\%$ 的数据，$1\leq n,q\leq 2\times 10^5$，$1\leq x,y,p\leq n$，$1\leq l\leq r\leq n$，$1\leq w\leq 10^4$。