Problem Description

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$.

Input Format

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 Format

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

10 10 7
4 2
10 4
3 2
6 10
9 2
7 3
1 4
8 2
5 3
8 10 10
2 6 2
3 6 2
4 6 4
3 10 2
8 8 10
3 10 4
2 3 2
2 6 4
1 7 10

0
2
0
1
7
0
2
0
1
0

Hint

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