[AdditionalFile5613.zip](file://AdditionalFile5613.zip?type=additional_file)

#5613. 「PA 2016 Final」Mrówki

标签: 传统 | 时间限制: 11000 ms | 内存限制: 256 MiB |

题目描述

题目译自 PA 2016 Final Mrówki

在 Stubajtowy 森林中，蚂蚁们建造了 $n$ 个蚁丘，编号为从 $1$ 到 $n$。这些蚁丘之间通过地下双向道路连接，使得任意两个蚁丘之间都恰好存在一条路径（即不经过重复道路且不往返）。

Stubajtowy 森林的蚁后下令对蚁丘的人员构成进行年度轮换。这次轮换涉及 $m$ 只工蚁：其中第 $i$ 只工蚁需要在时刻 $t_{i}$ 离开它目前所在的蚁丘 $a_{i}$，前往目的地蚁丘 $b_{i}$。所有的蚂蚁都以相同的速度匀速前进，且中途不会停下。

据推测，如果在路径上的某个点同时聚集了太多的蚂蚁，它们可能会产生「分裂」行为。在工蚁们出发之前，蚁后想知道对于其中的每一只工蚁，在它的整个行程中，同一时刻能与之相遇（即处于同一条道路的同一点，或处于同一个蚁丘内）的其他移动蚂蚁构成的集合的最大规模是多少。我们仅考虑旅途中的相遇：具体而言，如果第 $i$ 只蚂蚁在时刻 $t_{i}^{\prime}$ 到达目标蚁丘，那么我们只计算蚂蚁 $i$ 与蚂蚁 $j$ 在时间区间 $[t_{i}, t_{i}^{\prime}] \cap [t_{j}, t_{j}^{\prime}]$ 内发生的相遇。

输入格式

第一行包含两个整数 $n$ 和 $m$ $(1 \leq n, m \leq 100000)$，分别表示蚁丘的数量和参与轮换的蚂蚁数量。

接下来的 $n-1$ 行描述了蚁丘之间的道路网。每行包含三个整数 $u_{i}, v_{i}$ 和 $d_{i}$ $(1 \leq u_{i}, v_{i} \leq n, u_{i} \neq v_{i}, 1 \leq d_{i} \leq 10^{9})$，表示蚁丘 $u_{i}$ 和 $v_{i}$ 之间由一条道路连接，工蚁通过该道路需要 $d_{i}$ 个单位时间。

接下来的 $m$ 行描述了参与轮换的蚂蚁。第 $i$ 行包含三个整数 $a_{i}, b_{i}$ 和 $t_{i}$ $(1 \leq a_{i}, b_{i} \leq n, a_{i} \neq b_{i}, 1 \leq t_{i} \leq 10^{9})$。

输出格式

输出 $m$ 行。第 $i$ 行应包含一个整数，表示蚂蚁 $i$ 在其旅途中，同一时刻能遇到的其他移动蚂蚁（不包括自身）构成的最大集合的规模。

样例

输入

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

输出

2
2
2
1
0