CF1481F AB Tree 题解

Codeforces
Luogu

Description.

给定 \(n\) 个点的树,\(1\) 是根,染出 \(k\) 个白点 \(n-k\) 个黑点。
求出最少的本质不同的从根走到某个节点连成的字符串数,并构造。

Solution.

CF1481F AB Tree 题解

首先考虑没有 \(k\) 的限制,肯定每层染相同。
那么最小值肯定是 \(\max\{\text{dep}_i\}\)。
考虑最大值,发现最大可能是 \(\max\{\text{dep}_i\}+1\),证明参考下文构造。

所以直接背包判断最大值是不是 \(\max\{\text{dep}_i\}\),是就直接背包输出方案,否则就用另一种方法构造。
但是朴素背包是 \(O(\frac{n^2}\omega)\) 的,空间都开不下。
但是本质不同的数量是 \(O(\sqrt n)\) 的,优化成了 \(O(\sqrt n\log n\frac{n}{\omega})\)。
看上去很能过,就写了。

然后构造的话就直接按层构造,然后把叶子非叶子分开。
然后最左边、最上面全都染成黑色,否则染成白色。
考虑证明,分界点如果在叶子节点中,证明显然,否则证明显然。
然后就做完了。

Coding.

点击查看代码
//是啊,你就是那只鬼了,所以被你碰到以后,就轮到我变成鬼了{{{
#include<bits/stdc++.h>
using namespace std;typedef long long ll;
template<typename T>inline void read(T &x)
{
	x=0;char c=getchar(),f=0;
	for(;c<48||c>57;c=getchar()) if(!(c^45)) f=1;
	for(;c>=48&&c<=57;c=getchar()) x=(x<<1)+(x<<3)+(c^48);
	f?x=-x:x;
}
template<typename T,typename...L>inline void read(T &x,L&...l) {read(x),read(l...);}//}}}
const int N=100005;int n,K,rr[N],idt,rrt,vs[N],rs[N],dg[N];
bitset<N>dp[5266];vector<int>v[N],cn[N],id[N],e[N],vi;
inline void pull(int nw,int vl)
{
	if(nw==0) return;else if(dp[nw-1][vl]) pull(nw-1,vl);
	else rr[++rrt]=nw,pull(nw-1,vl-vi[nw-1]);
}
inline void dfs(int x,int d) {v[d].push_back(x);for(auto y:e[x]) dfs(y,d+1),dg[x]++,dg[y]++;}
int main()
{
	read(n,K),dp[0][0]=1;int mxd=0;for(int i=2,x;i<=n;i++) read(x),e[x].push_back(i);//dep 出现次数
	dfs(1,1);for(int i=1;i<=n;i++) if(!v[i].empty()) cn[v[i].size()].push_back(i),mxd=i;//出现次数次数
	for(int i=1;i<=n;i++) if(!cn[i].empty())//相当于多重背包的元素
	{
		int cnt=cn[i].size(),gg=0,nw=1;
		for(;gg<cnt;gg+=nw,nw<<=1)
		{
			++idt,vi.push_back(i*min(nw,cnt-gg));//第 idt 个背包里的所有 dep
			for(int j=gg;j<cnt&&j<gg+nw;j++) id[idt].push_back(cn[i][j]);
		}
	}
	for(int i=1;i<=idt;i++) dp[i]=dp[i-1]|(dp[i-1]<<vi[i-1]);
	int wh=0;for(int i=K;i>=0;i--) if(dp[idt][i]) {wh=i;break;}
	pull(idt,wh);for(int i=1;i<=rrt;i++) for(auto x:id[rr[i]]) vs[x]=1;
	if(wh==K)
	{
		printf("%d\n",mxd);
		for(int i=1;i<=n;i++) if(vs[i]) for(auto w:v[i]) rs[w]=1;
		for(int i=1;i<=n;i++) putchar('b'-rs[i]);
		return putchar('\n'),0;
	}else printf("%d\n",mxd+1);
	int fg=1,x=K,y=n-K;for(int i=1;i<=n;i++)
	{
		sort(v[i].begin(),v[i].end(),[](int a,int b){return dg[a]>dg[b];});
		x<y?swap(x,y),fg^=1:0;for(size_t j=0;j<v[i].size();j++)
			rs[v[i][j]]=fg,x--,(!x?swap(x,y),fg^=1:0);
	}
	for(int i=1;i<=n;i++) putchar('b'-rs[i]);
	return putchar('\n'),0;
}
上一篇:APP产品分析


下一篇:13. .class文件加载机制