CF1225F题解

· · 题解

考虑反着做，把树变回链，这和原问题是等价的。

假设一个点的所有儿子的子树已经恢复成链，想让我们可以让一条长链和任意一条短链合并，把长链下移到短链的末尾，产生短链长度的代价，得到一条更长的长链。继续此类操作，直到所有儿子全部合并，不难发现，这个过程中与短链合并的顺序对答案没有影响。

实现上，长链剖分，先递归短儿子，按访问顺序将点加入竹坯序列中，最后加入长儿子，得到竹坯序列。对于操作序列，可以在遍历每一个点的儿子 v 时，记录上一个递归的轻儿子，记为 las ，在操作序列中加入 len_{las} 个 v ，表示，长链合并至以 v 作为链头时（即还未遍历到的儿子都已合并到了 v 的链末尾， v 要向 las 合并），要将 v 下移 len_{las} 次。

代码

#include<bits/stdc++.h>
using namespace std;
int n,x,fa[100005],len[100005],son[100005],siz[100005];
vector<int>g[100005],tr,op;
void dfs1(int u){
    siz[u]=len[u]=1;
    for(int v:g[u]){
        dfs1(v);
        len[u]=max(len[u],len[v]+1);
        siz[u]+=siz[v];
        if(len[v]>len[son[u]])son[u]=v;
    }
}
void dfs2(int u){
    tr.push_back(u);
    if(!son[u]){
        return ;
    }
    int las=0;
    for(int v:g[u]){
        if(v==son[u])continue;
        for(int i=1;i<=len[las];i++)op.push_back(v);
        dfs2(v);
        las=v;
    }
    for(int i=1;i<=len[las];i++)op.push_back(son[u]);
    dfs2(son[u]);
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=2;i<=n;i++){
        cin>>x;x++;
        fa[i]=x;
        g[x].push_back(i);
    }
    dfs1(1);
    dfs2(1);
    for(int v:tr)cout<<v-1<<" ";
    cout<<"\n"<<op.size()<<"\n";
    for(int v:op)cout<<v-1<<" ";
    return 0;
}
/*
9
0 1 1 3 0 5 6 7
*/