abc280-f

It has been 850 days since the last update, the content of the article may be outdated.

ABC280-F-Pay or Receive

By xiaruize

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

分情况讨论

情况1

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

情况二

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

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

所以，$L \Rarr R$ 的距离 $=$ $L$ 到 $root$ 的距离 $+$ $root$ 到 $R$ 的距离

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

Code