题解 P6697 【[BalticOI 2020 Day2] 村庄】

· · 题解

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

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

首先考虑最小值：

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

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]);
}