首先因为 \(1\) 点是可以一次性到多个点的，因此不需要考虑 \(1\) 点的情况，而是转而分析 \(1\) 的每个子树的情况，最后取 \(\max\)。
那么对于每个子树，就有每个节点每个时刻至多存在 \(1\) 个点的性质了。
考虑如何去求解。
首先一个贪心的想法是肯定是每个蚂蚁越早到一个点越好。
于是一个想法是考虑在 dfs 的时候合并。
即维护子树 \(u\) 内叶子到 \(u\) 的时间 \(S\)，子树 \(v\) 内叶子到 \(v\) 的时间 \(T\)。
那么如果存在 \(x\in S\) 满足 \(x\in T\)，那么就钦定这个蚂蚁先不往上爬，而是等到 \(x + 1\) 时刻继续爬，即 \(x\leftarrow x + 1\) 直到 \(x\not \in T\)。
但是问题在于合并的次数太多了，这个合并的方法也不太好用数据结构维护（其实可以启发式合并 + 线段树二分做到 \(\mathcal{O}(n\log^2 n)\)）。
考虑到一个 \(x\in S\)，这个 \(x\) 会和许多其他集合 \(T\) 合并，但是合并操作都是若 \(x\in T\)，则 \(x\leftarrow x + 1\)。
那么这说明实际上各个集合是不区分的，那么就可以直接把所有的叶子放在根处合并。
即直接维护可重集合 \(S = \{\operatorname{dep}_u | u \operatorname{is\ leaf}\}\)，那么若 \(S\) 中存在 \(c(c\ge 1)\) 个 \(x\)，就直接钦定一个 \(x\) 到根，而剩下的 \(c - 1\) 个 \(x\) 就只能变为 \(x + 1\) 继续等待。
\(x\) 从小到大操作直到 \(S\) 为空，变为空的那个时刻就代表着最后一个叶子的蚂蚁跳到了根，这个时刻就是这个子树的答案。
容易发现这是与上述的递归合并过程等价的，因为这个让 \(c - 1\) 个 \(x\) 变为 \(x + 1\) 就代表着在合并过程中发现了其他的 \(x\) 选择了让步。
然后考虑优化 \(S\) 的变化的过程。
其实能够发现真正只关注每个 \(x\) 的个数 \(\operatorname{cnt}_x\)。
那么就可以直接递推，当 \(\operatorname{cnt}_x\ge 1\) 时有 \(\operatorname{cnt}_{x + 1}\leftarrow \operatorname{cnt}_{x + 1} + \operatorname{cnt}_x\)。
然后考虑一下这个过程中 \(x\) 最大会是多少。
一个很宽的上界是 \(\operatorname{size}(T) + \max \operatorname{dep}(T)\le 2\operatorname{size}(T)\)。
又因为 \(1\) 的所有子树 \(\operatorname{size}\) 之和 \(= n - 1\)。
所以可以知道实际上 \(\sum \max x\le 2n - 2\)。
于是时间复杂度就为 \(\mathcal{O}(n)\)。
#include<bits/stdc++.h>
const int maxn = 5e5 + 10;
std::vector<int> to[maxn];
int dep[maxn], cnt[maxn * 2], tot;
int dfs(int u, int fa) {
dep[u] = dep[fa] + 1;
if (to[u].size() == 1)
cnt[dep[u]]++, tot++;
int siz = 1;
for (int v : to[u])
if (v != fa)
siz += dfs(v, u);
return siz;
}
int main() {
int n; scanf("%d", &n);
for (int i = 1, x, y; i < n; i++)
scanf("%d%d", &x, &y), to[x].push_back(y), to[y].push_back(x);
int mx = 0;
for (int u : to[1]) {
int siz = dfs(u, 1);
for (int i = 1; ; i++) {
if (cnt[i])
tot--, cnt[i + 1] += cnt[i] - 1;
if (! tot) {
mx = std::max(mx, i); break;
}
}
memset(cnt + 1, 0, sizeof(int) * siz * 2);
}
return printf("%d\n", mx), 0;
}