P11541 [Code+#5] 路路的图

**题目来源：**[link](https://www.gitlink.org.cn/thusaa/codeplus5)。

路路是一个喜欢强连通分量的孩子。他非常喜欢对一张图求出其强连通分量。他认为这个操作是好的。但他并不是总有能力完成这件事。现在，路路给你一张图 $G$，希望你帮他求出这张图的每个强连通分量。由于这张图的边数特别的多，他不会直接输入这张图，而是告诉你它的构造方法： 给出一棵 $n$ 个点（编号为 $1$ 到 $n$）的无根树 $T$ 和 $m$ 条指令 $(a_i,b_i,c_i)$。图 $G$ 刚开始 $n$ 个点，编号也为 $1$ 到 $n$，并且没有边。对于每一条指令 $(a_i,b_i,c_i)$，如果在树上 $b_i$ 到 $x$ 的最短路径长度（经过的边数）不超过 $c_i$，那么你会在 $G$ 中加入一条从 $a_i$ 连向 $x$ 的有向边。 请你帮帮他。

第一行两个整数 $n$、$m$； 接下来 $n-1$ 行，每行两个整数 $a$、$b$，表示树 $T$ 中的一条边 $(a,b)$； 接下来 $m$ 行，每行三个整数 $a_i,b_i,c_i$，表示每一条指令。

你将会需要输出 $n$ 个整数。其中第 $i$ 个整数 $p_i$ 这么输出： - $p_1 = 1$； - 如果点 $i$ 和点 $1$、$2$、……、$(i-1)$ 都不在同一个强连通分量中，那么 $p_i = 1 + \max\{p_1,p_2,\cdots,p_{i-1}\}$； - 否则，假设 $i$ 和点 $j< i$ 在一个强连通分量中，并且和点 $1$、$2$、……、$(j-1)$ 都不在同一个强连通分量中，那么 $p_i = p_j$。

**数据范围：** $\def\arraystretch{1.21} \begin{array}{|c|c|c|}\hline \bold{\small{子任务}}&\textbf{score}&\textbf{constraints}\\\hline \text{A}&30&c_i\le n\le 50,m\le 100\\\hline \text{B}&30&c_i\le50\\\hline \text{C}&30&\small{无特殊限制}\\\hline \end{array}$ 对于所有数据，$n\le 10^5,m\le 2\times 10^5, c_i\le n$。 **样例解释：** 第一组指令往 $G$ 中加入了从 $5$ 连向每个点的有向边； 第二组指令往 $G$ 中加入了从 $1$ 连向 $1,2,3,4,5,6$ 的有向边； 第三组指令往 $G$ 中加入了从 $4$ 连向每个点的有向边； 最后的强连通分量为 $\{1,4,5\}$、$\{2\}$、$\{3\}$、$\{6\}$、$\{7\}$。 **注**：由于数据缺失，仅有 $9$ 组测试点。