正题

https://www.luogu.com.cn/problem/CF1481F

---

题目大意

给出 n n n个点的一棵树，在每个节点上填 a / b a/b a/b，要求恰好有 m m m个 a a a。要求每个节点到根路径上的字符串种类最少，输出方案。

1 ≤ m ≤ n ≤ 1 0 5 1\leq m\leq n\leq 10^5 1≤m≤n≤105

---

解题思路

被stoorz拉来做这题，被D了/kk

很顺理成章的一个思路是我们可以在同一深度的点填上相同的字母，如果能够做到答案到达下界就是最大深度。

但是显然不是所有时候都能到达下界，再考虑一个能确定上界的构造方法。我们从上往下填，当我们到达一层设有 x x x个非叶子节点，还剩下 m 0 m_0 m0​个 a a a和 m 1 m_1 m1​个 b b b那么显然有 m 0 + m 1 ≥ 2 x m_0+m_1\geq 2x m0​+m1​≥2x，也就是有 m a x { m 0 , m 1 } ≥ x max\{m_0,m_1\}\geq x max{m0​,m1​}≥x，所以这一层的非叶子节点一定能填相同的字母，然后叶子节点我们优先按照非叶子节点的字母填。如果够，那么这一层的贡献是 1 1 1，如果不够这一层会产生一个不同的，贡献为 2 2 2，但是此时有一种字母已经用完，所以剩下的层的贡献一定都是 1 1 1。

这样就发现答案的上界就是最大深度+1，问题就变为了如何判断答案是否是 k k k了。

暴力完全背包显然不可行，考虑从和为 n n n入手，相似与根号分治的思路我们可以考虑根号的复杂度。对于所有层来说节点数不同的值只有根号级别种，所以我们可以把这些合并出来变成一个多重背包问题，然后用单调队列的 O ( n m ) O(nm) O(nm)做法即可（但是由于这题是判断是否能够拼出来所以不需要单调队列甚至不需要枚举余数）。

时间复杂度： O ( n n ) O(n\sqrt n) O(nn ​)

---

code

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int N=1e5+10;
struct node{
	int to,next;
}a[N];
int n,m,k,p,tot,r[N],ls[N],f[500][N];
bool ans[N];vector<int>v[N],c[N];
void addl(int x,int y){
	a[++tot].to=y;
	a[tot].next=ls[x];
	ls[x]=tot;return;
}
void dfs(int x,int dep){
	k=max(k,dep);
	v[dep].push_back(x);
	for(int i=ls[x];i;i=a[i].next){
		int y=a[i].to;
		dfs(a[i].to,dep+1);
	}
	return;
}
void solve0(){
	for(int i=1;i<=n;i++)ans[i]=1;
	while(p&&m){
		int l=(m-f[p][m])/r[p];
		for(int i=0;i<l;i++)
			for(int j=0;j<v[c[r[p]][i]].size();j++)
				ans[v[c[r[p]][i]][j]]=0;
		m=f[p][m];p--;
	}
	printf("%d\n",k);
	for(int i=1;i<=n;i++)
		putchar(ans[i]+'a');
	return;
}
void solve1(){
	int u[2]={m,n-m};
	for(int d=1;d<=k;d++){
		int tmp=0,uc=0;
		for(int i=0;i<v[d].size();i++)
			tmp+=(ls[v[d][i]]!=0);
		if(tmp<=u[0])u[0]-=tmp;
		else{
			uc=1;u[1]-=tmp;
			for(int i=0;i<v[d].size();i++)
				if(ls[v[d][i]]!=0)ans[v[d][i]]=1;
		}
		for(int i=0;i<v[d].size();i++){
			if(ls[v[d][i]]!=0)continue;
			if(!u[uc])uc^=1;
			u[uc]--;ans[v[d][i]]=uc;
		}
	}
	printf("%d\n",k+1);
	for(int i=1;i<=n;i++)
		putchar(ans[i]+'a');
	return;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=2,x;i<=n;i++)
		scanf("%d",&x),addl(x,i);
	dfs(1,1);
	for(int i=1;i<=k;i++)c[v[i].size()].push_back(i);
	for(int i=1;i<=m;i++)f[0][i]=-1;
	for(int i=1;i<=n;i++){
		if(!c[i].size())continue;
		r[++p]=i;
		for(int j=1;j<=m;j++)f[p][j]=-1;
		for(int j=1;j<=m;j++){
			if(f[p-1][j]!=-1)f[p][j]=j;
			else if(j>=i&&f[p][j-i]!=-1&&j-f[p][j-i]<=i*c[i].size())
				f[p][j]=f[p][j-i];
		}
	}
	if(f[p][m]!=-1)solve0();
	else solve1();
	return 0;
}