QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 128 MB

# 7453. rplexq

统计

给定一棵 $n$ 个节点的有根树,第 $i$ 个点的编号是 $i$。

有 $m$ 次询问,每次询问给出 $l,r,x$,求有多少点编号的二元组 $(i,j)$ 满足 $l \le i < j \le r$ 且 $i$ 和 $j$ 的最近公共祖先是节点 $x$。

输入格式

第一行三个数 $n$ $m$ $rt$,其中 $rt$ 表示根节点的编号。

之后 $n-1$ 行,每行两个数 $u$ $v$ 表示一条边。

之后 $m$ 行,每行三个数 $l$ $r$ $x$ 表示一次询问。

输出格式

共 $m$ 行,表示每个询问对应的答案

样例数据

样例输入

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

样例解释

2 6 2:符合条件的有 $(2,4)$,$(2,6)$。

4 6 4:符合条件的有 $(4,6)$ 。

3 10 2:符合条件的有 $(4,8)$ ,$(4,9)$,$(6,8)$,$(6,9)$,$(8,9)$,$(8,10)$,$(9,10)$。

3 10 4:符合条件的有 $(4,6)$,$(4,10)$。

2 6 4:符合条件的有 $(4,6)$。

子任务

Idea:Ynoi,Solution:nzhtl1477,Code:nzhtl1477,Data:nzhtl1477

对于 $100\%$ 的数据,$1\le n,m\le 2\cdot 10^5$,$1 \le l,r,x \le n$。