CF1225F题解

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

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

实现上，长链剖分，先递归短儿子，按访问顺序将点加入竹坯序列中，最后加入长儿子，得到竹坯序列。对于操作序列，可以在遍历每一个点的儿子

v

时，记录上一个递归的轻儿子，记为

las

，在操作序列中加入

len_{las}

个

v

，表示，长链合并至以

v

作为链头时（即还未遍历到的儿子都已合并到了

v

的链末尾，

v

要向

las

合并），要将

v

下移

len_{las}

次。

代码

CPP

#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
*/

文章操作

相关推荐

评论

CF1225F题解