Sol
令 \(k=\left\lceil\sqrt{n}\right\rceil\)。
首先注意到环相当容易做,直接 DFS 生成树,然后判断是否有点对 \((a,b)\) 满足 \(a\) 是 \(b\) 的祖先且 \(dis_{a,b}>=k\)。
如果不存在环,那么就意味着对于任何一个点,他能到的点数一定小于 \(k\),从下往上做即可。
令 \(k=\left\lceil\sqrt{n}\right\rceil\)。
首先注意到环相当容易做,直接 DFS 生成树,然后判断是否有点对 \((a,b)\) 满足 \(a\) 是 \(b\) 的祖先且 \(dis_{a,b}>=k\)。
如果不存在环,那么就意味着对于任何一个点,他能到的点数一定小于 \(k\),从下往上做即可。