Link.
Description.
给定 \(n\) 个点的树，\(1\) 是根，染出 \(k\) 个白点 \(n-k\) 个黑点。
求出最少的本质不同的从根走到某个节点连成的字符串数，并构造。
Solution.
首先考虑没有 \(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;
}