# 树上的容限路径

时间限制：1 秒。内存限制：128 MiB。参考 [评测环境与性能](../../../docs/评测环境与性能.md)。

## 背景故事

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

(本故事由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$ 个整数，按顶点编号给出答案。

## 样例 1

### 输入

```text
4 5
1 2
2 3
3 4
0 0
0 0
1 1
0 0
1 0
1 2
2 1
3 2
3 3
```

### 输出

```text
2 4 3 2
```

## 样例 2

### 输入

```text
1 0
-1000000000 1000000000
```

### 输出

```text
1
```

## 样例 3

### 输入

```text
3 0
1 2
2 3
0 0
0 0
0 0
```

### 输出

```text
1 1 1
```

## 样例解释

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

![实线表示基础树边；花括号列出可选特殊边权。顶点2的零容限不能填补集合中的空缺。](assets/example.svg)

实线表示基础树边；花括号列出可选特殊边权。顶点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）；补全范围、边编号输入格式、重复权值、空路线及第一步语义。

| 分值 | 额外限制 |
| --- | --- |
| 20% | $n\le8,\ m\le15$ |
| 30% | $n\le100,\ m\le1000$ |
| 50% | 无额外限制 |