前言
咱 OI 生涯独立做出来的第二道黑题，给孩子激动坏了，赶紧交一篇题解。
可能不算最优解（甚至会被卡空间），但是是一个比较符合正常人思路的题解
思路
首先我们需要猜出一个结论，同一深度的点肯定尽可能相同（咱想了好久才想到）。为什么呢？如果没有 $a$ 的数量的限制的话，只要每个深度的字符都一样，答案肯定是 $dep$。但是如果有 $a$ 的数量的限制的话，我们就需要修改一些 $a$ 变成 $b$ 或者反过来。
第二个结论比较好猜，要修改来满足 $a$ 的个数的点，肯定尽可能靠下方。因为一个点修改后会影响它和它的子树内的所有点对应的字符串，显然影响越少越好。
看题解还有第三个结论，最多只会有一层点为了满足 $a$ 的限制而修改。咱没有发现这个性质，但是并不影响做题。事实上这个结论挺好想的，如果必须修改两层才能满足要求的话，有一层必定填满，那么它的字符也相同了。
集齐了三大性质后我们就来做题了。咱把题目分成了两部分来做，先“整块”地确定每一层应该统一填 $a$ 还是 $b$，然后“散块”地确定哪些地方要为了满足 $a$ 的数量的要求而取反。
每一层可以选为 $a$ 带来 $size$（层的大小）个 $a$ 的贡献，或者不选带来 $0$ 个 $a$ 的贡献，显然是一个背包模型。然而发现背包大小为 $n$，物品有 $n$ 个，复杂度 $O(n^2)$，无法通过。
然后就到了咱认为是本体精髓的地方了，每当到这种遇到状态数带来的时空复杂度瓶颈，咱们都可以大胆猜测状态数很少（举两个例子，淘金 的状态数；一个数 $x$ 最多有 $\log_2 x$ 个质因数）。因为很多时候状态数之间会有一种函数关系，导致最终时空复杂度其实是可以保证的。
回到本题来，我们大胆推测大小（含义是某一层的节点个数）不同的物品实际很少，因为不同大小最优取 $1,2,3 \dots$ 时只有 $\sqrt n$ 个不同物品。那如果有很多个相同物品呢？比如说一条链的情况？我们这时候把它看做一个多重背包，合并大小相同的物品并二进制处理。最终我们只会有大概 $\sqrt n$ 个物品（二进制分组带来的 $\log$ 影响很小，很多时候是负贡献，思考一下）
于是我们直接背包。咱没有使用各位大佬的 bitset 优化，而是直接开了一个 int 数组（记住这个 int 的伏笔）记录前驱，这样也方便输出方案（各位应该知道通过记录前驱可以输出背包的方案）。
背包完毕了以后，我们可以通过“整块”分配出某些 $a$ 的个数，可能这些值并不等于 $x$，我们选择一个最接近 $x$ 的然后补泉剩下的差值。我们通过拆分背包的方案知道了对于大小为 $size$ 的层数，有多少个需要分配为泉部都是 $a$，剩下的泉部都是 $b$。具体怎么分配呢？同样大小的层数可能有很多个耶。
咱没有看到别的巨佬在这里思考，可能是咱想多了吧。假设我们背包出来的值小于 $x$，说明需要多一些 $a$，那么我们需要把 $b$ 改为 $a$，又希望改变的地方尽可能深度大（第二个结论，这样影响更小）。所以当背包出来的值小于 $x$ 的时候，把泉部为 $a$ 的节点放在上方，反之则反过来做。
然后我们把从下往上枚举，通过取反某些字符来补上背包出来的值和 $x$ 的差值，然后输出就好啦~糟糕的是咱有了方案竟然不知道怎么输出第一个答案（可以通过第三个性质算）......一个哈希给水过去了（
很可恶，毒瘤题卡咱空间！咱调了半天甚至想用 bool + unsigned short 卡空间，最后发现只需要微调一下数组大小就卡过去了......算啦，能过就好~
总结
思维难度主要在第一个结论和“大胆猜测”上面，其实第一个结论看上去就很 CF/AT（）第二个则是 OI 的一点小套路吧，记得遇到状态数瓶颈猜一猜状态数不多就行。
代码
代码非常丑陋，也没有闲心去调了......
说实话命名规范很不好让人看不懂（咱最讨厌这种代码了），如果有不明白含义的变量可以在讨论区问......
#include<bits/stdc++.h>
#define Akano 1
#define pure__Elysia 0
#define loves ^
using namespace std;
using pis = pair<int,string>;
using ull = unsigned long long;
const int MAXN = 1e5 + 2;
const int MAXSEC = 600;
const int INF = 1e8;
const int base = 31;
const ull key = 101811082121;
struct Edge{
int nxt,to;
}e[MAXN * 2];
int head[MAXN],cnt;
inline void AddEdge(int from,int to){
e[++cnt].to = to;
e[cnt].nxt = head[from];
head[from] = cnt;
return ;
}
int n,x,fa[MAXN],dep[MAXN],sizeofDep[MAXN],maxDep,sizCnt[MAXN];
int f[MAXSEC][MAXN];
int tail,object[MAXSEC],sizeofObject[MAXSEC],timesofObect[MAXSEC],useTime[MAXN],siz[MAXN];
char chs[MAXN],chstr[MAXN];
ull hashVal[MAXN];
inline ull Shift(ull x){
x ^= x << 7;
x ^= x >> 11;
x ^= x << 13;
x ^= x >> 17;
return x;
}
vector<int> points[MAXN];
void GetHash(int u){
hashVal[u] = (Shift(hashVal[fa[u]]) ^ key) * base + (chstr[u] - 'a');
for(int i = head[u];i;i = e[i].nxt){
const int v = e[i].to;
GetHash(v);
}
return ;
}
inline pis GetAns(int st){
int u = st,pre = 0;
for(int i = tail+1;i >= 2;i--){
pre = u,u = f[i][u];
if(pre != u){//走了这个叶子
useTime[sizeofObject[i-1]] += timesofObect[i-1];
}
}
if(st > x){//需要把a变成b,尽可能把a放在下面
for(int i = maxDep;i >= 1;i--){
if(useTime[sizeofDep[i]] > 0){
useTime[sizeofDep[i]]--;
chs[i] = 'a';
}else{
chs[i] = 'b';
}
}
}else{
for(int i = 1;i <= maxDep;i++){
if(useTime[sizeofDep[i]] > 0){
useTime[sizeofDep[i]]--;
chs[i] = 'a';
}else{
chs[i] = 'b';
}
}
}
for(int i = 1;i <= n;i++){
chstr[i] = chs[dep[i]];
}
if(st > x){//需要从a改变为b
for(int i = maxDep;i >= 1 && st > x;i--){
if(chs[i] == 'a'){
for(auto j : points[i]){
st--;
chstr[j] = 'b';
if(st <= x)break;
}
}
}
}else if(st < x){
for(int i = maxDep;i >= 1 && st < x;i--){
if(chs[i] == 'b'){
for(auto j : points[i]){
st++;
chstr[j] = 'a';
if(st >= x)break;
}
}
}
}
pis ret;
for(int i = 1;i <= n;i++){
ret.second += chstr[i];
}
set<ull> _set;
GetHash(1);
for(int i = 1;i <= n;i++){
_set.insert(hashVal[i]);
}
ret.first = _set.size();
return ret;
}
bool CmpBySiz(int x,int y){
return siz[x] < siz[y];
}
void dfs(int u){
siz[u] = 1;
dep[u] = dep[fa[u]] + 1;
maxDep = max(maxDep,dep[u]);
sizeofDep[dep[u]]++;
for(int i = head[u];i;i = e[i].nxt){
const int v = e[i].to;
dfs(v);
siz[u] += siz[v];
}
return ;
}
int main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>x;
if(n == 1){
cout<<1<<endl;
if(x == 1){
cout<<'a'<<endl;
}else{
cout<<'b'<<endl;
}
return not(Akano loves pure__Elysia);
}
for(int i = 2;i <= n;i++){
cin>>fa[i];
AddEdge(fa[i],i);
}
dfs(1);
for(int i = 1;i <= n;i++){
points[dep[i]].push_back(i);
}
for(int i = 1;i <= maxDep;i++){
sort(points[i].begin(),points[i].end(),CmpBySiz);
}
for(int i = 1;i <= maxDep;i++){
sizCnt[sizeofDep[i]]++;
}
for(int i = 1;i <= n;i++){
if(sizCnt[i] == 0)continue;
int now = 1,nowv = i,res = sizCnt[i];
while(now <= res){
object[++tail] = nowv;
sizeofObject[tail] = i;
timesofObect[tail] = now;
res -= now;
now *= 2,nowv *= 2;
}
if(res > 0){
object[++tail] = i * res;
sizeofObject[tail] = i;
timesofObect[tail] = res;
res = 0;
}
}
for(int i = 0;i <= n;i++){
f[1][i] = -1;
}
f[1][0] = 1;
for(int i = 1;i <= tail;i++){
for(int j = 0;j <= n;j++){
f[i+1][j+1] = -1;
}
for(int j = 0;j <= n;j++){
if(f[i][j] == -1)continue;
f[i+1][j] = j;
}
for(int j = 0;object[i] + j <= n;j++){
if(f[i][j] == -1)continue;
f[i+1][object[i] + j] = j;
}
}
for(int delta = 0;delta <= n;delta++){
pis ans = make_pair(INF,"unInitialized");
if(x - delta >= 0 && f[tail+1][x - delta] != -1){
ans = GetAns(x - delta);
}else if(x + delta <= n && f[tail+1][x + delta] != -1){
ans = GetAns(x + delta);
}
if(ans.first != INF){
cout<<ans.first<<endl<<ans.second<<endl;
break;
}
}
return not(Akano loves pure__Elysia);
}
Comments NOTHING