P6782 [Ynoi2008] rplexq

Given a rooted tree with $n$ nodes, the index of node $i$ is $i$. There are $m$ queries. Each query gives $l, r, x$. You need to count how many pairs of node indices $(i, j)$ satisfy $l \le i < j \le r$, and the lowest common ancestor of $i$ and $j$ is node $x$.

The first line contains three integers $n$ $m$ $rt$, where $rt$ is the index of the root node. The next $n - 1$ lines each contain two integers $u$ $v$, representing an edge. The next $m$ lines each contain three integers $l$ $r$ $x$, representing a query.

Output $m$ lines. Each line is the answer to the corresponding query.

Idea: Ynoi, Solution: nzhtl1477, Code: nzhtl1477, Data: nzhtl1477. Constraints: for $100\%$ of the testdata, $1 \le n, m \le 2 \cdot 10^5$, $1 \le l, r, x \le n$. #### Sample Explanation #### `2 6 2`: the valid pairs are $(2,4)$, $(2,6)$. `4 6 4`: the valid pair is $(4,6)$. `3 10 2`: the valid pairs are $(4,8)$, $(4,9)$, $(6,8)$, $(6,9)$, $(8,9)$, $(8,10)$, $(9,10)$. `3 10 4`: the valid pairs are $(4,6)$, $(4,10)$. `2 6 4`: the valid pair is $(4,6)$. Translated by ChatGPT 5