AT_agc009_d [AGC009D] Uninity 题解

一道妙妙题。

一句话题意：求点分树的高度最小值。

给所有点填上一个数表示它子树 \(k\)，考虑一种填法什么时候满足条件，发现当且仅当任意两对值相同的点之间的路径上存在一个权值更大的点。

考虑随便找一个点作为根从叶子节点开始贪心填值，每次选择能填的最小值，发现这样填最终的值的最大值一定是最小的。

在每个点 \(x\) 上对每个 \(\le \log n\) 的值维护一下子树中是否存在一个这个值的点满足到 \(x\) 的路径上没有一个值更大的点，即可求出 \(x\) 能填的最小的值，时间复杂度 \(\mathcal O(n\log n)\)。

参考代码：

#include<bits/stdc++.h>
#define mxn 200003
#define pb push_back
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define rept(i,a,b) for(int i=(a);i<(b);++i)
using namespace std;
int n,ans,f[mxn],s[mxn];
vector<int>g[mxn];
void dfs(int x,int fa){
	int a=0;
	for(int i:g[x])if(i!=fa){
		dfs(i,x);
		rept(j,0,18)if((a>>j)&1&&(s[i]>>j)&1)f[x]=max(f[x],j+1);
		a|=s[i];
	}
	while((a>>f[x])&1)f[x]++;
	ans=max(ans,f[x]);
	s[x]=((a>>f[x])<<f[x])|(1<<f[x]);
}
signed main(){
	scanf("%d",&n);
	for(int i=1,x,y;i<n;++i){
		scanf("%d%d",&x,&y);
		g[x].pb(y),g[y].pb(x);
	}
	dfs(1,0);
	cout<<ans;
	return 0;
}