Codeforces
Luogu
给定 \(n\) 个点的树,\(1\) 是根,染出 \(k\) 个白点 \(n-k\) 个黑点。
求出最少的本质不同的从根走到某个节点连成的字符串数,并构造。
首先考虑没有 \(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})\)。
看上去很能过,就写了。
然后构造的话就直接按层构造,然后把叶子非叶子分开。
然后最左边、最上面全都染成黑色,否则染成白色。
考虑证明,分界点如果在叶子节点中,证明显然,否则证明显然。
然后就做完了。
//是啊,你就是那只鬼了,所以被你碰到以后,就轮到我变成鬼了{{{ #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; }