前言
这是一道神仙题
我翻阅的很多分题解,包括Atcoder官方题解
都没有看懂,应该是因为我比较菜
然后我看懂了这篇(地址放在文末)
方法可能和主流略有不同 但我觉得这个办法更好理解
题面
题面大意
定义一个单独的节点为一棵Uninity 0的树。
将\(x(x \geq 0)\)棵Uninity k的树全部连到一个节点上形成的树,称之为一棵Uninity k+1的树。
显然,一棵Uninity k的树,同样也是一棵Uninity k+1,k+2,k+3...的树。
现在给你一棵树,求一个最小的k使得这棵树是一棵Uninity k的树。
样例 #1
样例输入 #1
7
1 2
2 3
2 4
4 6
6 7
7 5
样例输出 #1
2
样例 #2
样例输入 #2
12
1 2
2 3
2 4
4 5
5 6
6 7
7 8
5 9
9 10
10 11
11 12
样例输出 #2
3
提示
数据范围
- $ 2\ ≦\ N\ ≦\ 10^5 $
- $ 1\ ≦\ a_i,\ b_i\ ≦\ N(1\ ≦\ i\ ≦\ N-1) $
解法
需要知道的一些性质
- 一颗点分树的最深深度的点是\(log n\)级别的
证明:点分树的定义可得
点分树是通过更改原树形态使树的层数变为稳定 \log n 的一种重构树。 ——OI wiki
- 两个标号相等的点之间肯定有一个标号严格小于他们的标号的点
证明:点分树的过程里面可以证明这一点 画个图就出来了
做法
我们将每一个点的标号,记为在这个点在这颗点分树的深度
利用性质二,可以建出一颗树。我们不妨把所有的节点编号给反过来 叶子结点是0 这样我们就会将这个结论反过来,变成:
两个标号相等的点之间肯定有一个标号严格大于他们的标号的点
我们不妨设\(F_{i, j}\)为从\(i\)的子树的节点到\(i的路径上还有多少个标号为\)j$的点没有被消灭掉,即没有严格大于的点。
注意,这里第二位只需开到\(\log n\)级别,由性质1可以得到。
然后发现\(F\)这个数组是叠加的
所以我们遍历子树以后叠加\(F\)值
如果我们在一颗子树(以\(i\)为根)里面找到 \(\geq 2\) 个点(即\(F_{i, j} \geq 2\))
那么由性质2,我们可以得到这颗子树里面的最小可能的最大标号是\(j + 1\),这个\(j\) 我们枚举得到
现在我们找到了最大的那个值(设它为\(lim\)),然后我们再往上找,知道找到了一个不存在的,就是最大的,再换句话就是在往上一个就会存在不合法。
然后我们将以\(i\)为根的子树的点个所有\(j(j \leq lim - 1)\)的点给清空掉,然后更新答案就行了
外话:我不知道那篇题解里面为什么要加一个s[]
数组,我删掉以后也过了
代码
# include<bits/stdc++.h>
using namespace std;
# define N 100005
# define LOG 20
# define ADD for (int _ = 0; _ < LOG; ++_)
vector<int> G[N];
int n, lim, ans, f[N][LOG];
inline void dfs (int u, int fa) {
for (int v : G[u]) {
if (v == fa) continue;
dfs (v, u);
ADD {
f[u][_] += f[v][_];;
}
}
lim = 0;
ADD {
if (f[u][LOG - 1 - _] > 1) {
lim = LOG - _;
break;
}
}
while (f[u][lim]) {
++lim;
}
ADD {
if (_ == lim) {
break;
}
f[u][_] = 0;
}
++f[u][lim];
ans = max (ans, lim);
}
signed main() {
cin >> n;
for (int i = 1, u, v; i < n; ++i) {
cin >> u >> v;
G[u].push_back(v);
G[v].push_back(u);
}
dfs (1, 0);
cout << ans << endl;
return 0;
}