对于前 20% 的部分分， k ≤ 3 ，进行（简单的）分类讨论即可。 首先，只有出现在 k 个信息里的 2k 个编号是有用的，可以进行离散化。 将信息 a; b; c 看作从 a 连到 b 的长度为 c 的边，显然每个弱连通块之间是 独立的，可以分开处理。对于每个连通块，我们可以通过一遍 dfs 计算出每个 点的相对深度。如果在 dfs 的过程中递归到同一个点时计算出的深度不同，答 案就是”No”。（这一步也可以通过带权并查集完成） 如果仅仅实现上述算法，只能通过 subtask2（甚至无法通过样例）。考虑一 个简单的反例即样例的第三个测试点： 1 → 2 → 4; 1 → 3 → 4 ，每条边的边权 都是 1 。此时 dep1 = 0; dep2 = dep3 = 1; dep4 = 2。发现不合法的本质原因是出 现了 2 → 4; 3 → 4 这样的结构，即如果把边看成双向的， dep2 = dep3 且 2 和 3 在只保留 dep ≥ dep2 的点的情况下连通。 不难猜想合法的充要条件：计算出唯一的相对深度后对于任意 u 和 v 满足 depu = depv ， u 和 v 无法只通过 depw ≥ depu = depv 的 w 互相到达。有这个结 论后可以通过 subtask3。 1为了加速上述检查过程，考虑按深度从大到小加入点和边，并用并查集维 护当前每个连通块里最小的 dep 。如果 merge 两个不同的连通块时这两个连通 块里最小的 dep 相等，就出现了不合法的情况。这样就可以通过所有数据了。