题目简述：给定简单（无自环、无重边）连通无向图$G = (V, E), 1 \leq n = |V| \leq 2.5 \times 10^5, 1 \leq m = |E| \leq 5 \times 10^5$，保证任意节点的度数$\geq 3$。给定参数$1 \leq k \leq n$，要求完成以下任务之一：
1. 找到一条包含至少$\frac n k$个节点的简单路径。
2. 找到$k$个简单环，使得
2.1. 每个环包含少于$\frac n k$个节点，且包含的节点个数不得被$3$整除；
2.2. 每个环都存在一个代表节点，这个节点不在其他环中出现。
解：考虑图$G$的DFS树$T$。
1. 若$T$中存在深度$\geq \frac n k$的节点（根节点深度为$1$），则找到了一条包含至少$\frac n k$个节点的简单路径，完成任务1。
2. 不然（即，树$T$的深度$< \frac n k$），$T$存在至少$k$个叶节点（设$T$有$x$个叶节点，则
$$n = |V| = |T| \leq \sum_{v \text{ is a leaf of } T} \text{depth}(v) < x \frac n k, $$
从而$x > k$）。
CodeForces 1103C. Johnny Solving
原文：https://www.cnblogs.com/TinyWong/p/10348575.html