AGC009D Uninity 做题记录

如下定义一棵树的海胆度：

• 一个单点的海胆度是 $0$；
• 一棵树的海胆度是最小的 $k$ 满足删掉其某个节点后剩下的连通块的海胆度都 $\le k-1$；

给定一棵 $n$ 个点的树，求它的海胆度。

$1\le n\le 10^5$。

相当于找到最小的颜色数 $k$，使得给每个点染 $[1,k]$ 中的颜色，要求任意两个颜色均为 $x$ 的点之间路径上颜色的最大值 $>x$。

考虑这样一个不是很显然的贪心：

• 随便定一个根，自底向上确定每个点的颜色：
  • 对于点 $u$，其颜色确定为只考虑其子树时的最小的合法颜色；

具体的，每个点维护一个集合 $ban_u$，表示 $u$ 的子树内还未被覆盖的颜色，即所有满足存在 $col_v=x$ 且 $v\to u$ 链上不存在颜色 $>x$ 的点的 $x$ 组成的集合。

那么 $u$ 儿子的 $ban$ 对 $col_u$ 仅有如下限制：

1. $\forall v\in son_u$，$col_u\not\in ban_v$
2. $\forall v_1,v_2\in son_u,v_1\not=v_2$，$col_u>\max\limits_{x\in \left(ban_{v_1}\cap ban_{v_2}\right)} x$

并且确定了 $col_u$ 之后就可以确定 $ban_u=\{col_u\}\cup\{x|x> col_u,\exist v\in son_u,x\in ban_v\}$，即所有儿子的 $ban$ 的并加上 $col_u$，再清除 $<col_u$ 的元素。

而显然 $k\le \log n$，所以可以用二进制记录 $ban$，使用 __builtin 的位运算即可做到 $O(n)$。

代码如下：

#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

const int S=100005;

int n;
vector<int> g[S];
int f[S],ans;

void dfs(int u,int fa)
{
	int d=0;
	for(int v:g[u]) d+=(v!=fa);
	if(d==0) f[u]=1;
	else
	{
		int ban=0,big=0;
		for(int v:g[u])
			if(v!=fa)
			{
				dfs(v,u);
				big|=ban&f[v];
				ban|=f[v];
			}
		int t;
		if(big==0) t=0;
		else t=32-__builtin_clz(big);
		int tmp=ban;
		tmp>>=t;
		tmp^=(1<<20)-1;
		int res=__builtin_ctz(tmp)+t;
		ans=max(ans,res);
		f[u]=((1<<res)|ban)>>res<<res;
	}
}

int main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<=n-1;i++)
	{
		int x,y;
		cin>>x>>y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	dfs(1,0);
	cout<<ans<<'\n';
	return 0;
}