自动搬运

查看原文

来自洛谷，原作者为

	王奕清 没有我，你的生活会怎样？

搬运于2025-08-24 22:23:10，当前版本为作者最后更新于2020-11-02 16:04:37，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

提供一种十分简单的做法：

我们先把村庄看成一个个节点，然后就是对每个点找一个不同的节点去移动，贡献是两个节点之间的距离，问可能贡献的最大值和最小值，以及方案。

首先考虑最小值：

对于一个子树的根节点，他的每个儿子最多只会上传自己这一个节点来请求移动，原因等下再说，然后：

1.如果我的儿子中有需要匹配的，那么就把我和他们放到一个环上，第$i$个需要匹配的儿子向第$i+1$个要匹配的儿子移动，然后最后一个儿子向根移动，根向第一个儿子移动。贡献+=2*儿子数

2.如果没有要匹配的，就把我上传。

所以每个儿子最多上传一个节点，但是，根节点不能上传，那我们就判断一下，如果他没有移动过，就把他放到他第一个儿子的环中，具体实现细节可以看代码

void dfs1(int x,int y)
{
	vector<int>p;
	for(int i=0;i<v[x].size();i++)
	{
		int h=v[x][i];
		if(h==y)continue;
		dfs1(h,x);
		if(!a1[h])p.push_back(h);//需要上传
	}
	if(p.empty())return;//情况2
	for(int i=0;i<p.size()-1;i++)a1[p[i]]=p[i+1];
	a1[p.back()]=x,a1[x]=p.front(),s1+=2*p.size();
}
void work1()
{
	dfs1(1,0);
	if(!a1[1])a1[1]=a1[v[1][0]],a1[v[1][0]]=1,s1+=2;
}

再考虑最大值：

一句话，以任一点为根，求出dfs序，然后每个节点向dfs序比自己大n/2的节点移动。

void dfs2(int x,int y)
{	
	dfn[++*dfn]=x;
	sz[x]=1;
	for(int i=0;i<v[x].size();i++)
	{
		int h=v[x][i];
		if(h==y)continue;
		dfs2(h,x);
		sz[x]+=sz[h];
	}
	s2+=2*min(n-sz[x],sz[x]);
}
void work2()
{
	dfs2(1,0);
	for(int i=1;i<=n;i++)a2[dfn[i]]=dfn[(i+n/2-1)%n+1];
}

为什么这么简单呢，具体原因有点玄学，因为树中必定有一个重心， 而贡献要最大，那么对于以重心为根的树来说，每个点一定要向和自己不在一个子树的点移动（这里的子树是指重心的子树，即失去重心后，树会被分成几个联通块），那么如果当前我选的这个根不是重心，那么对于一个重心来说，他的父亲以上的那些点一定<n/2个，所以我的dfs序+n/2后，一定不在某一个同样的子树中。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 100005
int n,x,y,a1[N],s1,a2[N],dfn[N],sz[N],s2;
vector<int>v[N];
void dfs1(int x,int y)
{
	vector<int>p;
	for(int i=0;i<v[x].size();i++)
	{
		int h=v[x][i];
		if(h==y)continue;
		dfs1(h,x);
		if(!a1[h])p.push_back(h);
	}
	if(p.empty())return;
	for(int i=0;i<p.size()-1;i++)a1[p[i]]=p[i+1];
	a1[p.back()]=x,a1[x]=p.front(),s1+=2*p.size();
}
void work1()
{
	dfs1(1,0);
	if(!a1[1])a1[1]=a1[v[1][0]],a1[v[1][0]]=1,s1+=2;
}
void dfs2(int x,int y)
{	
	dfn[++*dfn]=x;
	sz[x]=1;
	for(int i=0;i<v[x].size();i++)
	{
		int h=v[x][i];
		if(h==y)continue;
		dfs2(h,x);
		sz[x]+=sz[h];
	}
	s2+=2*min(n-sz[x],sz[x]);
}
void work2()
{
	dfs2(1,0);
	for(int i=1;i<=n;i++)a2[dfn[i]]=dfn[(i+n/2-1)%n+1];
}
signed main()
{
	cin>>n;
	for(int i=1;i<n;i++)
	{
		cin>>x>>y;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	work1(),work2();
	printf("%lld %lld\n",s1,s2);
	for(int i=1;i<=n;i++)printf("%lld ",a1[i]);puts("");
	for(int i=1;i<=n;i++)printf("%lld ",a2[i]);
}