P12205 [COI 2022] 通行证件 / Vinjete

译自 [HIO (COI) 2022](https://hsin.hr/hio2022/zadaci/) T4。

Gospodin Malnar 计划在亚洲旅行，访问 $N$ 个城市。这些城市通过 $N-1$ 条双向高速公路连接，形成一棵树。城市编号为 $1$ 到 $N$，起点为 $1$。 亚洲有 $M$ 种不同类型的通行证，编号从 $1$ 到 $M$。每条高速公路 $i$ 需要购买编号在 $[l_i,r_i]$ 范围内的所有通行证才能通过，第 $i$ 条公路连接 $a_i,b_i$ 两点。 你的任务是确定从起点到其他城市 $i$ $(2 \leq i \leq N)$ 所需购买的最少通行证数量。

第一行包含两个整数 $N$ 和 $M$，表示城市数和通行证种类数。 接下来 $N-1$ 行，每行包含四个整数 $a_i, b_i, l_i, r_i$，表示一条高速公路及其所需通行证区间。

输出 $N-1$ 行，第 $i$ 行表示从城市 $1$ 到城市 $i+1$ 所需的最少通行证数量。

【样例解释】 样例 $1$： - 到城市 $2$ 的路径覆盖区间 $[2,4]$，需 $3$ 个通行证 $(2,3,4)$。 - 到城市 $3$ 的路径覆盖 $[1,4]$，需 $4$ 个。 - 到城市 $4$ 的路径合并 $[2,4]$ 和 $[3,5]$，结果为 $[2,5]$，需 $4$ 个 $(2,3,4,5)$。 - 到城市 $5$ 的路径包含 $[2,4]$ 和 $[5,6]$，合并后需 $5$ 个。 - 到城市 $6$ 的路径合并 $[1,4]$ 和 $[2,3]$，结果为 $[1,4]$，需 $4$ 个。 样例 $2$： - 到城市 $2$ 只需区间 $[2,2]$，$1$ 个通行证。 - 到城市 $3$ 合并 $[2,2]$ 和 $[3,3]$，共 $2$ 个。 - 到城市 $4$ 需合并 $[2,2]$, $[3,3]$, $[1,1]$，总覆盖 $[1,3]$，需 $3$ 个。 - 到城市 $5$ 的路径覆盖 $[1,5]$，需 $5$ 个。 【数据规模与约定】 对于所有数据，满足 $1 \leq N \leq 10^5$,$1 \leq M \leq 10^9$,$1 \leq a_i, b_i \leq N$, $1 \leq l_i \leq r_i \leq M$，且道路构成一棵树。 | 子任务编号 | 分值 | 附加限制 | | :---------: | :----: |:-------- | | $1$ | $11$ | $N \leq 10^3$, $M \leq 10^3$ | | $2$ | $13$ | $N \leq 10^3$, $M \leq 10^9$ | | $3$ | $16$ | $N \leq 5 \times 10^4$, $M \leq 5 \times 10^4$ | | $4$ | $29$ | $N \leq 10^5$, $M \leq 10^5$ | | $5$ | $31$ | $N \leq 10^5$, $M \leq 10^9$ |