ABC280-F-Pay or Receive

By xiaruize

很容易可以想到先用并查集处理联通块，下文中将默认讨论对于每个联通块内的处理

分情况讨论

情况1

如图，当存在一个环，使得围着这个环一圈的路径的 disdis 值 ≠0\neq 0 ，那么，容易发现，这个联通块上的所有的两点距离一定为 infinf

情况二

对于这种情况，只需要选择一个’根节点’，并记录每个节点到它的距离，显然这个距离唯一(否则这个图满足情况一)

因为图满足这个性质: 一条边正反两次经过的代价为0

所以，L⇒RL \Rarr R 的距离 == LL 到 rootroot 的距离 ++ rootroot 到 RR 的距离

而上述的距离用 dfsdfs 在 O(n)O(n) 的时间下求出

Code