1103C

`2023-09-05 14:52:07 solution` 找路径很好找，我们随便跑个 dfs 树找个深度 $\ge \frac{n}{k}$ 的路径输出即可。 可是怎么找 $k$ 个长度不是 $3$ 的倍数的环呢？既然我们跑了 dfs 树，那么就没有横叉边，对于叶子节点非树边只有返祖边，然后一看 ......

任取一颗 $\text{DFS}$ 树。 如果最大深度 $\geq\frac{n}{k}$，则找到了一条路径。 对于剩下的情况，我们按环去处理。钦定一个合法环中的“代表点”为 $k$ 个环中只出现过一次的点。 考虑让叶子作为环的代表点。我们寻找到了一些性质：由于树高 $ 点击查看代码 ``` #in ......