[R15F]树上炸弹 - 代码源竞赛平台

时空限制

3S/512M

题目描述

给定一棵由 $n$ 个节点和 $n-1$ 条无向边组成的树。

定义一条路径的长度为路径上边的数量，定义节点 $i$ 和节点 $j$ 的距离 $\text{dis}(i,j)$ 为 $i$ 和 $j$ 之间最短路径的长度。

有 $m$ 个炸弹，第 $i$ 个炸弹位于节点 $p_i$，爆炸范围为 $w_i$，会炸到满足 $dis(p_i,j)\leq w_i$ 的任意节点 $j$。一个节点上可能存在多个炸弹。

求每个节点会被多少个炸弹炸到。

格式

输入格式

第一行包含两个整数 $n,m$，分别表示节点的数量和炸弹的数量。

接下来 $n-1$ 行每行包含两个整数 $u_i,v_i$，表示节点 $u_i$ 和节点 $v_i$ 之间有一条无向边。数据保证这 $n-1$ 条边构成一棵 $n$ 个节点的树。

接下来 $m$ 行每行包含两个整数 $p_i,w_i$，表示第 $i$ 个炸弹所在的节点和爆炸范围。

输出格式

输出 $n$ 个整数，第 $i$ 个整数表示节点 $i$ 会被多少个炸弹炸到。

样例

样例输入 #1

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

样例输出 #1

1 3 5 2 4

样例解释 #1

第 $1$ 个炸弹会炸到节点 $2,3,4,5$。

第 $2$ 个炸弹会炸到节点 $1,2,3$。

第 $3$ 个炸弹会炸到节点 $2,3,4,5$。

第 $4$ 个炸弹会炸到节点 $3,5$。

第 $5$ 个炸弹会炸到节点 $3,5$。

数据规模

对于 $40\%$ 的数据，$n,m\leq 5000$。

对于 $100\%$ 的数据，$1\leq n,m\leq 5\times 10^5$，$1\leq u_i,v_i,p_i\leq n$，$1\leq w_i\leq 50$。