#1746. 树数术

    ID: 1746 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest1089来源:qoj.ac数据:公开样例线段树

树数术

树数术

题目描述

标题: 树数术 - Problem - QOJ.ac

#5403. 树数术

Statistics

The problem was used in the following contests:

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

给定一个长度为 m 的正整数序列 a1,⋯,am,满足 ∀i,ai∈[1,n]。

q 次询问,每次询问给出 2k 个数 l1,r1,⋯,lk,rk,满足 ∀i,1≤li≤ri≤m。

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

  • 1≤i≤s。
  • ∀1≤j≤i,bi=bj 或者 bi 为 bj 的祖先节点。

输入格式

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

接下来 n−1 行,每行两个正整数 xi、yi,表示一条连接 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,∑k≤100000。

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

对于所有测试数据,满足 n,m,∑k≤700000。

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

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