QOJ.ac

QOJ

Time Limit: 4.5 s Memory Limit: 1024 MB Total points: 100

# 5403. 树数术

统计

给定一棵 $n$ 个点的树,树上的节点依次编号为 $1$ 到 $n$。这一颗树的根节点为 $1$。

给定一个长度为 $m$ 的正整数序列 $a_1, \cdots, a_m$,满足 $\forall i$,$a_i \in [1,n]$。

$q$ 次询问,每次询问给出 $2k$ 个数 $l_1, r_1, \cdots, l_k, r_k$,满足 $\forall i$,$1 \leq l_i \leq r_i \leq m$。

我们不妨记数组 $a$ 中由这 $k$ 个子区间拼接而成的序列 $a_{l_1}, a_{l_1+1}, \cdots, a_{r_1}, a_{l_2}, a_{l_2+1}, \cdots, a_{r_2},\cdots, a_{l_k}, a_{l_k + 1}, \cdots, a_{r_k}$ 为 $b_1, \cdots, b_s$,你需要求出有几个 $i$ 满足如下条件:

  • $1 \leq i \leq s$。
  • $\forall 1 \leq j \leq i$,$b_i = b_j$ 或者 $b_i$ 为 $b_j$ 的祖先节点。

输入格式

第一行三个正整数 $n$、$m$、$q$。

接下来 $n-1$ 行,每行两个正整数 $x_i$、$y_i$,表示一条连接 $x_i, y_i$ 的树边。

接下来一行有 $m$ 个数,依次表示 $a_1, \cdots, a_m$。

接下来 $q$ 行,每行第一个正整数表示 $k$,之后 $2k$ 个正整数,依次表示 $l_1, r_1, l_2, r_2, \cdots, l_k, r_k$。

输出格式

$q$ 行,每行一个数表示这一次询问答案。

样例数据

样例输入

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

样例输出

4
2
2

子任务

由于本题数据规模可以达到 27MB,请注意自己的 IO 用时。

Subtask 1($10\%$):给定的树是一条链。

Subtask 2($20\%$):$k = 1$。

Subtask 3($30\%$):$n,m,\sum k \leq 100\,000$。

Subtask 4($40\%$):无特殊限制。

对于所有测试数据,满足 $n,m,\sum k \leq 700\,000$。