CF1387B1 Solution

题目链接

题解

贪心呐，策略是由倒数第二层节点向上递归，将所有未交换的子节点与递归到的节点互换。若根节点未移动，则将其与任意子节点互换即可。

简单证明：节点(i)一定需要和与它一条边即可相邻的节点（父结点或子节点）交换。设节点(i)深度为(d_i)，且(d_{i-2})及以下的节点全部处理完毕（也就是只剩下它和它的子节点啦），现在证明(i)一定要且只要与没有换的子节点互换。因为没有换的节点与它的儿子换代价会(+2)，与(i)换也会(+2)，所以对该子节点来说和(i)换没有坏处且(i)还可牵连受益。已经换了的子节点与(i)换的话代价会(+2)且这样仅使(i)节点受益，而(i)与其父结点换的话也会(+2)这样在满足(i)的同时还可使其父结点受利，因此与换了的子节点交换没有好处。又及，因为是由下向上互换，代价只增不减，每次(+2)。

AC代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int fst[N],nxt[2*N],v[2*N],cnt; 
int ans[N],id[N],sum;//id[i]:节点i初始位置的当前节点编号,sum:答案距离
void add(int x,int y)
{
	v[++cnt]=y;
	nxt[cnt]=fst[x],fst[x]=cnt;
}
void dfs(int x,int fa)
{
	for(int i=fst[x];i;i=nxt[i])
	{
		int y=v[i];
		if(y==fa) continue;
		dfs(y,x);
		if(id[y]==y) 
		{
                	id[y]=id[x],id[x]=y; 
            		sum+=2;
       		}
	}
}
int main()
{
	int n,x,y;
	scanf("%d",&n);
	for(int i=1;i<n;i++)
	{
		scanf("%d%d",&x,&y);
		add(x,y),add(y,x);
	}
	for(int i=1;i<=n;i++) id[i]=i;
	dfs(1,0);
	if(id[1]==1) 
	{
		id[1]=id[v[fst[1]]],id[v[fst[1]]]=1; 
		sum+=2;
	}
	for(int i=1;i<=n;i++) ans[id[i]]=i;
	printf("%d
",sum);
	for(int i=1;i<=n;i++) printf("%d ",ans[i]);
	return 0;
}