QOJ.ac

QOJ

Time Limit: 4.5 s Memory Limit: 1024 MB Total points: 100
[+6]

# 5403. 树数术

统计

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

给定一个长度为 m 的正整数序列 a1,,am,满足 iai[1,n]

q 次询问,每次询问给出 2k 个数 l1,r1,,lk,rk,满足 i1lirim

我们不妨记数组 a 中由这 k 个子区间拼接而成的序列 al1,al1+1,,ar1,al2,al2+1,,ar2,,alk,alk+1,,arkb1,,bs,你需要求出有几个 i 满足如下条件:

  • 1is
  • 1jibi=bj 或者 bibj 的祖先节点。

输入格式

第一行三个正整数 nmq

接下来 n1 行,每行两个正整数 xiyi,表示一条连接 xi,yi 的树边。

接下来一行有 m 个数,依次表示 a1,,am

接下来 q 行,每行第一个正整数表示 k,之后 2k 个正整数,依次表示 l1,r1,l2,r2,,lk,rk

输出格式

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,k100000

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

对于所有测试数据,满足 n,m,k700000