题目描述

S 国有 $n$ 个城市，城市之间有 $n-1$ 条道路连接，保证所有城市连通。首都为 $1$ 号城市，即树根。国家里有 $m$ 座信号塔：用 $x, y$ 表示 $x$ 有一座辐射为 $y$ 的信号塔，此时 $x$ 子树内与它距离不超过 $y$ 的城市的信号将会增加 $1$。$q$ 次询问 $x$ 城市子树内与它距离不超过 $y$ 的城市的信号之和是多少。

输入格式

第一行三个正整数 $n,m,q$，含义见上。

接下来 $n-1$ 行每行两个整数 $s_i,t_i$，表示树的一条边。

接下来 $m$ 行每行两个整数 $x_i,y_i$，给出一座信号塔的信息。

接下来 $q$ 行每行两个整数 $x_i,y_i$，表示一组询问。

输出格式

输出 $q$ 行，每行一个整数表示第 $i$ 个询问的答案。

输入输出样例

输入样例

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

输出样例

9
9
9
3
4
4
3
13

大样例

数据规模与约束

对于所有的数据，有 $n,m,q\le 3\times 10^5,1\le s_i,t_i,x_i,y_i\le n$。

Subtask $1$（$30$pts）：$n,m,q\le 3000$。

Subtask $2$（$10$pts）：树是一条链。

Subtask $3$（$20$pts）：树的生成方式为第 $i$ 个点从 $[1,i-1]$ 中随机选取一个点作为父亲。

Subtask $4$（$40$pts）：无特殊性质。