思路

选择坐标正方向从队伍前方指向后方，条件 $(a,b,d)$ 就要求 $x_b-x_a=d$。建立从 $a$ 到 $b$、权值为 $d$ 的边，以及从 $b$ 到 $a$、权值为 $-d$ 的边。

一个连通分量中的所有相对坐标都由任意一个起点的坐标决定。不同连通分量之间没有约束，因此可以分别将各自起点设为 $0$。

做法

维护访问标记和 64 位整数坐标。枚举所有士兵，每遇到一个尚未访问的点，就把它的坐标设为 $0$，加入队列，开始一次广度优先遍历。

从 $u$ 沿权值为 $d$ 的边到达 $v$ 时：若 $v$ 未被访问，则令 $x_v=x_u+d$ 并入队；若 $v$ 已被访问，则检查 $x_v$ 是否等于 $x_u+d$。任何一条边不满足等式时，答案为 NO；所有分量的全部边都满足时，答案为 YES。

边必须按输入完整保留，重边可能一致也可能矛盾。不能只搜索包含士兵 $1$ 的分量，不能把零坐标当作未访问标记，也不能认为 $m\le n$ 就代表每个分量至多有一个环。使用队列可以避免长链上的递归栈溢出。

正确性证明

在一个分量中固定起点坐标为 $0$，不会损失任何方案：任意可行方案都可以将该分量的全部坐标减去起点坐标，而不改变任何坐标差。

遍历到一个新点时，连接它的边要求它的坐标必须等于已经确定的前驱坐标加边权。因此归纳可知，算法赋出的每个坐标都是任何起点坐标为 $0$ 的可行方案必须采用的值。

若算法发现某条边的等式不成立，两端的坐标又已经被之前的边强制确定，则不存在同时满足这些条件的方案。若所有边都通过检查，算法构造出的坐标直接满足每条输入条件，因而就是一组合法安排。对所有分量分别执行以上过程，得到全题答案。

部分分做法

子任务 1 中，每个分量选最小编号点为坐标 $0$。沿生成树的简单路径至多经过 $n-1$ 条边，所以其他点的坐标一定落在 $[-(n-1),n-1]$ 内。枚举其余点的整数坐标，直接检查全部条件即可；赋值过程中也可以提前检查两端均已赋值的等式。

子任务 2 可以使用稠密矩阵，保存两个点之间目前已知的位移。用 Floyd 式枚举中间点，合并两条已知路径；若已有位移与新路径的位移不同，就产生矛盾。若闭包过程中没有矛盾，则同一分量内所有路径的位移一致，可据此构造坐标。

子任务 3 中，条件只连接相邻编号。将端点按编号递增排列，并在必要时将 $d$ 取反。对于每对相邻编号，只要它们的所有条件要求同一个位移，就可以依次选择每个相邻间隙的大小；没有条件的间隙可以任意选择。用有序映射保存各间隙的要求即可。这里仍需检查重复条件是否冲突。

一般情形使用上述迭代图遍历，也可以用维护到根坐标差的带权并查集。

复杂度

满分做法中，每个点进入队列一次，每条输入条件对应两条有向边，各处理一次，所以时间复杂度为 $O(n+m)$，空间复杂度为 $O(n+m)$。所有测试的总复杂度为 $O(\sum n)$，因为每组都有 $m\le n$。

坐标的绝对值可能达到 $(n-1)\times10^9$，必须使用 64 位整数。稠密闭包的时间、空间复杂度分别为 $O(n^3)$、$O(n^2)$；相邻编号分支采用有序映射时为 $O(m\log n)$ 时间、$O(m)$ 空间。