迷宫

题目背景

某一天，善良的lxw来到了一个包含 $n$ 个结点的树形迷宫。于是他邀请了 $m$ 个信竞同学来走这个迷宫。

对于lxw的每个同学，第 $i$ 个同学的起点为 $s_i$，终点为 $t_i$。游戏开始时，所有人在第 $0$ 秒同时从自己的起点出发，以每秒跑一条边的速度，不间断地沿着最短路径向着自己的终点跑去，跑到终点后该玩家就算完成了任务。 (由于地图是一棵树，所以每个人的路径是唯一的)

但是lxw发现迷宫里的每个结点都被被善良的某佬放上了防摸鱼检测器，被检测器发现的人将会受到严厉的惩罚

幸运的是，节点 $j$ 的检测器只在第 $w_j$ 秒启动。只有当一个人在第 $w_j$ 秒也正好到达了结点 $j$ 的时候，他才会被检测到。lxw 想知道有多少人可能会受到严厉的惩罚?

注意：我们认为一个人到达自己的终点后就会结束游戏，他不能等待一段时间后再被检测到。 即对于把结点 $j$ 作为终点的玩家：若他在第 $w_j$ 秒前到达终点,则在结点 $j$ 的观察员不能观察到该玩家；若他正好在第 $w_j$ 秒到达终点,则在结点 $j$ 的检测器可以检测到这个玩家。

---

written by chen_zhe

题目描述

给一棵树和 $m$ 条路径，树上每个点有一个值 $W_i$ 。问对于每一个点，询问有多少条路径的第 $W_i+1$个点是这个点。

输入格式

第一行有两个整数 $n$ 和 $m$。其中 $n$ 代表迷宫（树）的结点数量, 同时也是检测器的数量, $m$ 代表人的数量。

接下来 $n-1$ 行每行两个整数 $u$ 和 $v$，表示结点 $u$ 到结点 $v$ 有一条边。

接下来一行 $n$ 个整数，其中第 $j$ 个整数为 $w_j$ , 表示结点 $j$ 检测器启动的时间。

接下来 $m$ 行，每行两个整数 $s_i$，和 $t_i$，表示一个人的起点和终点。

对于所有的数据，保证 $1\leq s_i,t_i\leq n, 0\leq w_j\leq n$。

输出格式

输出 $1$ 行 $n$ 个整数，第 $j$ 个整数表示结点 $j$ 的检测器可以检测到多少人。

样例 #1

样例输入 #1

6 3
2 3
1 2 
1 4 
4 5 
4 6 
0 2 5 1 2 3 
1 5 
1 3 
2 6

样例输出 #1

2 0 0 1 1 1

样例 #2

样例输入 #2

5 3 
1 2 
2 3 
2 4 
1 5 
0 1 0 3 0 
3 1 
1 4
5 5

样例输出 #2

1 2 1 0 1

提示

【样例1说明】

对于 $1$ 号点，$w_i=0$，故只有起点为 $1$ 号点的人才会被观察到，所以玩家人 $1$ 和人 $2$ 被观察到，共有 $2$ 人被观察到。

对于 $2$ 号点，没有人在第 $2$ 秒时在此结点，共 $0$ 人被观察到。

对于 $3$ 号点，没有人在第 $5$ 秒时在此结点，共 $0$ 人被观察到。

对于 $4$ 号点，人 $1$ 被观察到，共 $1$ 人被观察到。

对于 $5$ 号点，人 $1$ 被观察到，共 $1$ 人被观察到。

对于 $6$ 号点，人 $3$ 被观察到，共 $1$ 人被观察到。

【子任务】

每个测试点的数据规模及特点如下表所示。 提示: 数据范围的个位上的数字可以帮助判断是哪一种数据类型。