树上的容限路径¶

时间限制：1 秒。内存限制：128 MiB。参考评测环境与性能。

背景故事¶

传感器沿树形线路传递信号。每段线路提供若干可选信号强度，传感器只允许强度变化落在自己的容限区间内。分别从每个传感器出发，统计信号能到达多少个位置。

(本故事由GPT-6重写)

给定一棵有 \(n\) 个顶点的无向树，树边按输入顺序编号 \(1,\ldots,n-1\) .另有 \(m\) 条无向特殊边，每条依附于一条树边，连接该树边的两个端点，并具有整数权值。允许同一树边上有多条特殊边，也允许它们的权值相同；没有特殊边的树边不能通行。

顶点 \(v\) 有容限 \([L_v,R_v]\) .从一个顶点出发，只能沿特殊边行走，每条基础树边至多经过一次。第一条特殊边的权值不受限制；以后在顶点 \(v\) 将权值为 \(p\) 的边接到权值为 \(w\) 的边时，必须满足

\[ L_v\le w-p\le R_v. \]

分别对每个起点，统计至少存在一条合法路线可以到达的顶点数。起点本身通过空路线可达，计入答案。每个终点可使用不同的路线和特殊边选择。

第一行包含 n m .接下来 \(n-1\) 行，每行 u v 表示一条树边。接下来 \(n\) 行，第 \(v\) 行包含 L_v R_v .最后 \(m\) 行，每行 e w 表示依附于第 \(e\) 条树边、权值为 \(w\) 的特殊边。

输出一行 \(n\) 个整数，按顶点编号给出答案。

2 4 3 2

1 0
-1000000000 1000000000

1 1 1

样例1中，从1无法越过2：可到达2的最后边权只有0和2，都不能以零变化接到边权1。从2出发却可以沿边权1、2依次到达3、4。因此可达关系未必对称。

实线表示基础树边；花括号列出可选特殊边权。顶点2的零容限不能填补集合中的空缺。

\(1\le n\le1000\) ，\(0\le m\le20000\) ，\(-10^9\le L_v\le R_v\le10^9\) ，\(|w|\le10^9\) .输入的基础图保证是一棵树。\(n=1\) 时必有 \(m=0\) .

规格重新设计：Codex（GPT-6）；补全范围、边编号输入格式、重复权值、空路线及第一步语义。