AB Tree
_ANIG_
·
·
题解
传送门
首先考虑答案最小能是多少。
如果 $n$ 个点都是同一种字母，则答案为 $m$（$m$ 表示最大深度）。
我们肯定希望统一层的字母都相同，这样这一层就不会产生新的字符串。
如果能找到若干层，使得这些层能恰好放这么多个 '$a$'，那么答案就是 $m$。
接着考虑答案最大是多少。
显然，如果有某一层有不同的字母，我们要尽量把与众不同的字母放到同一层叶子节点，这样答案只会增大 $1$。并且这些叶子节点是足够把剩余的没有分配的 '$a$' 放完的。
这样，可以先求出来是否存在若干层的节点数和恰好等于 $k$，如果存在，直接这些层的点全填成 '$a$'，否则就先找到小于 $k$，最大能填到几，再在剩余的层里找到叶子节点最多的一层，把剩余的都填到叶子节点上。
这样复杂度是 $O(n^2)$ 的。
有一个树上经典的优化：
若第 $i$ 层的节点数为 $w_i$，则 $w_i$ 只有 $\sqrt n$ 种不同的取值。
当然把节点数换成度数也是可以这样优化的。
于是可以转化为多重背包，复杂度 $O(n\sqrt n)$。
可能炸空间，可以让 $k$ 和 $n-k$ 取个 $\min$，这样就减了一半常数。
```cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5;
int n,m,dep[N],fa[N],w[N],g[N],k,sm[N],idx,qz[N],op,gg,nd,mk[N];
char rs[N];
bool f[600][N/2];
signed zy[600][N/2];
vector<int>p[N],q[N],dy[N],yy[N];
void solve(int x){
mk[x]=1;
for(int i=0;i<q[x].size();i++)rs[q[x][i]]='a'+op;
}
void solve(int x,int y){
for(int i=0;i<y;i++)solve(dy[x][i]);
}
void dfs(int x){
w[dep[x]]++;m=max(m,dep[x]);
q[dep[x]].push_back(x);
if(!p[x].size())g[dep[x]]++,yy[dep[x]].push_back(x);
for(int i=0;i<p[x].size();i++){
int c=p[x][i];
dep[c]=dep[x]+1;
fa[c]=x;
dfs(c);
}
}
signed main(){
cin>>n>>k;
if(k>n-k)k=n-k,op=1;
for(int i=2;i<=n;i++){
int x;
scanf("%lld",&x);
p[x].push_back(i);
}
dep[1]=1;
dfs(1);
for(int i=1;i<=m;i++)sm[w[i]]++,dy[w[i]].push_back(i);
f[0][0]=1;
for(int i=1;i<=n;i++){
if(!sm[i])continue;
idx++;
memset(qz,-0x3f,sizeof(qz));
for(int j=0;j<=k;j++){
if(j<i){
if(f[idx-1][j])qz[j]=j;
}else{
if(f[idx-1][j])qz[j]=j;
else qz[j]=qz[j-i];
}
}
for(int j=0;j<=k;j++){
if(qz[j]>=j-i*sm[i]){
f[idx][j]=1;
zy[idx][j]=(j-qz[j])/i;
}
}
}
for(int i=1;i<=n;i++)rs[i]='b'-op;
if(f[idx][k]){
cout<<m<<endl;
for(int i=n;i>=1;i--){
if(!sm[i])continue;
solve(i,zy[idx][k]);
k-=zy[idx][k]*i;idx--;
}
}else{
cout<<m+1<<endl;
for(int i=k;i>=1;i--)if(f[idx][i]){
nd=k-i,k=i;
break;
}
for(int i=n;i>=1;i--){
if(!sm[i])continue;
solve(i,zy[idx][k]);
k-=zy[idx][k]*i;idx--;
}
for(int i=1;i<=m;i++){
if(mk[i])continue;
if(gg==0||g[gg]<g[i])gg=i;
}
for(int i=0;i<nd;i++)rs[yy[gg][i]]='a'+op;
}
for(int i=1;i<=n;i++)putchar(rs[i]);
}
```