追踪足迹

暗网铺设完毕后，屏幕上出现了无数条发光的路径——像有人在这张网上走过，留下了脚印。Echo说，那是Zero的巡逻者，每天沿着固定的路线巡视核心防护网。

"我们要追踪他们。"你说，"找到他们经过每个节点的次数。"

"追踪足迹？"CC问。

"对。"你说，"每个巡逻者从一个起点出发，跑到一个终点。他们的路径会经过很多节点。我们要统计，每个节点被多少条路径踩过。"

"这就像……"CC想了想，"像数脚印。每个矿工从通道的一头走到另一头，我们要算每块地面被踩了多少次。"

"对。"

你开始写。对于每个巡逻者的路径，从起点走到终点，路径上的每个节点都被踩过一次。为了快速统计，用差分法——起点加一，终点加一，最近交汇点减二。最后把所有差分值汇总，就得到每个节点被踩的总次数。

屏幕上跳出了结果。第47号节点被踩了47次。

"又是47。"CC说。

"那是Zero的核心节点。"Echo说，"所有巡逻者都必须经过它。"

"那我们就从47号节点入手。"你说。

"不。"Echo说，"47号节点是陷阱。它被踩得最多，但守卫也最严。我们要找的是……被踩得最少的节点。"

"哪个？"

"第1号。"Echo说，"只被踩过一次。那是Zero的盲区。"

题目描述

$n$ 个节点的树。$m$ 个巡逻者，每个从 $s_i$ 跑到 $t_i$。求每个节点被多少条路径经过。

输入格式

$n, m$。然后 $n-1$ 条边。然后 $m$ 行，每行 $s_i, t_i$。

输出格式

$n$ 个整数，第 $i$ 个表示节点 $i$ 被经过的次数。

输入样例

3 2
1 2
2 3

输出样例

0 0 0

提示

• 树上差分。对每个查询 $(u, v)$：$cnt[u]++, cnt[v]++, cnt[lca]-=2$。
• 最后做一次DFS汇总子树和。
• 时间复杂度 $O((n+m) \log n)$。

"盲区找到了。"你说。

"1号节点。"CC说，"最小的地方。"

"最小的地方。"Echo说，"往往是最安全的。"

CC站起来，把服务器背在肩上——像背一个孩子。

"走。"她说，"去1号节点。"

[第三题：绕行防线]