P6071 "MdOI R1" Treequery

Given an undirected tree with $n$ nodes, where each edge has a weight. Let $E(x,y)$ denote the set of all edges on the simple path between $x$ and $y$ in the tree. In particular, when $x=y$, $E(x,y)=\varnothing$. You need to answer $q$ queries **online**. Each query gives $p,l,r$. Please compute the sum of edge weights of all edges in the set $\bigcap_{i=l}^r E(p,i)$, i.e. the sum of edge weights contained in the intersection of $E(p, l\dots r)$. In simple terms, you need to find the length of the common part of the simple paths from $p$ to every node in $[l,r]$.

The first line contains two integers $n,q$, representing the number of nodes in the tree and the number of queries. The next $n-1$ lines each contain three integers $x,y,w$, indicating that there is an edge between $x$ and $y$ with weight $w$. The next $q$ lines each contain three integers $p_0,l_0,r_0$. For the $i$-th query, the actual $p,l,r$ are obtained by XOR-ing $p_0,l_0,r_0$ with $lastans$, respectively, where $lastans$ is the answer to the previous query and is initially $0$.

For each query, output one integer per line, representing the answer.

[Sample 1 Explanation] The tree in the sample is shown in the figure:  In the explanations below, all query parameters are the real values after XOR with $lastans$. For the first query, $p=2$, $l=3$, $r=5$, and $\bigcap_{i=3}^5 E(2,i)$ is the edge $(2,3)$, with total length $3$. For the second query, $p=1$, $l=2$, $r=4$, and $\bigcap_{i=2}^4 E(1,i)$ is the edge $(1,3)$, with total length $2$. For the third query, $p=2$, $l=5$, $r=5$, and $\bigcap_{i=5}^5 E(2,i)$ is the edge set $\{(2,3),(3,1),(1,5)\}$, with total length $6$. For the fourth query, $p=3$, $l=3$, $r=4$, $\bigcap_{i=3}^4 E(3,i)=\varnothing$, and the total length is $0$. --- [Constraints] **This problem uses bundled testdata.** | Subtask ID | $n,q\leq$ | Special Property | Score | | :--------: | :-------: | :--------------: | :---: | | 1 | $10^5$ | $l=r$ | 8 | | 2 | $10^5$ | $p=1$ | 20 | | 3 | $10^3$ | None | 20 | | 4 | $10^5$ | None | 26 | | 5 | $2\times 10^5$ | None | 26 | For $100\%$ of the data, $1\leq n,q\leq 2\times 10^5$, $1\leq x,y,p\leq n$, $1\leq l\leq r\leq n$, and $1\leq w\leq 10^4$. Translated by ChatGPT 5