[ABC362F] Perfect Matching on a Tree 讲解

zrl123456 · 2024-07-15 22:20:05 · 题解

[ABC362F] Perfect Matching on a Tree

题目考察：dfs，重心。
题目简述：
给你一棵 n 个点的树，选出 \displaystyle\lfloor\frac{n}{2}\rfloor\times2 个点，这些点两两不同，有 \displaystyle\lfloor\frac{n}{2}\rfloor 个点设为 \{x_{\lfloor\frac{n}{2}\rfloor}\}，另外 \displaystyle\lfloor\frac{n}{2}\rfloor 个点设为 \{y_{\lfloor\frac{n}{2}\rfloor}\}，使得 \displaystyle\sum_{i=1}^{\lfloor\frac{n}{2}\rfloor}\text{dist}(x_i,y_i) 最大。
其中 \text{dist}(x,y) 表示从点 x 到点 y 所经过的最少边数。
数据范围：

• 2\le n\le 2\times 10^5

  首先我们猜想，若 \displaystyle\sum_{i=1}^{\lfloor\frac{n}{2}\rfloor}\text{dist}(x_i,y_i) 最大，则从 x_i 到 y_i 的这条路径一定经过了这棵树的重心。
  证明：
  我们设根节点为重心，再设从 x_k 到 y_k 的这条路径没有经过这棵树的重心，则一定有一从 x_j 到 y_j 的路径不与其相交，因为若所有 x_i 到 y_i 的路径都与其相交，则所有的点对中要么有至少一个点在 x_k 和 y_k 的子树内（然而这是不可能的，因为根据重心的定义，不会有一个子树的大小超过 \displaystyle\lfloor\frac{n}{2}\rfloor），要么所有的点都能在不经过重心的情况下到达 x_k 到 y_k 的路径上的一个点（然而这也是不可能的，因为这个点、x_k 和 y_k 路径上的一个点和重心形成了一个环，这不符合树的定义）。总而言之，所有 x_i 到 y_i 的路径两两相交。
  下面我们继续来证明选重心为根节点存在最优解。若不选重心作伪根节点，则有一组 x_k 和 y_k 没有经过重心，那么我们找来一组 x_j 和 y_j（x_j 和 y_j 都不在 x_k 和 y_k 所在的子树内），将 y_j 与 y_k 交换，若存在最优解，则 \text{dist}(x_j,y_j)+\text{dist}(x_k,y_k)<\text{dist}(x_j,y_k)+\text{dist}(x_k,y_j)。
  下面我们来证明该式成立（下面设点 u 的深度为 dep_u，u 和 v 的 LCA 为 \text{lca}(u,v)）：

  \text{dist}(x_j,y_j)+\text{dist}(x_k,y_k)=dep_{x_j}+dep_{y_j}+dep_{x_k}+dep_{y_k}-2dep_{\text{lca}(x_k,y_k)}

  而：

  \text{dist}(x_j,y_k)+\text{dist}(x_k,y_j)=dep_{x_j}+dep_{y_j}+dep_{x_k}+dep_{y_k}

  因为 dep_{\text{lca}(x_k,y_k)}>0，所以 \text{dist}(x_j,y_j)+\text{dist}(x_k,y_k)<\text{dist}(x_j,y_k)+\text{dist}(x_k,y_j)。
  证毕。

由于选择重心的话最后的答案是相同的（甚至选一个最大子树的大小不大于 \displaystyle\lfloor\frac{n}{2}\rfloor 都可以），上面已经证明，答案是 \displaystyle\sum_{i=1}^{\lfloor\frac{n}{2}\rfloor}dep_{x_i}+dep_{y_i}，则我们在其里面任选一个即可。

那么我们考虑如何选出这些点对，由于重心的基本性质没有任意一颗子树的大小超过 \displaystyle\lfloor\frac{n}{2}\rfloor，所以我们设 \{dfn_n\} 为以树的重心为根所得的前序遍历，则点 dfn_i 和点 \displaystyle dfn_{i+\lfloor\frac{n}{2}\rfloor} 一定不在一个子树内，所以将 dfn_i 和 \displaystyle dfn_{i+\lfloor\frac{n}{2}\rfloor} 放在一组是没有问题的。
如果 n 是奇数怎么办？由于答案是 \displaystyle\sum_{i=1}^{\lfloor\frac{n}{2}\rfloor}dep_{x_i}+dep_{y_i}，所以我们要丢弃最小的 dep_i，于是我们丢弃根节点（重心）。

时间复杂度为 \Theta(n)。
代码：

#include<bits/stdc++.h>
#define inl inline
#define reg register
#define int long long
#define fst ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define rep(i,x,y) for(reg int i=x;i<=(y);++i) 
#define per(i,x,y) for(reg int i=x;i>=(y);--i)
#define rpr(i,x,y,z) for(reg int i=x;i<=(y);i+=z)
#define epe(i,x,y,z) for(reg int i=x;i>=(y);i-=z)
#define repe(i,x,y) for(i=x;i<=(y);++i) 
#define endl '\n'
#define INF 1e16
#define pb push_back
#define fi first
#define se second
#define lcm(x,y) x/__gcd(x,y)*y
#define ull unsigned long long
#define prr make_pair
#define pii pair<int,int> 
#define gt(s) getline(cin,s)
#define at(x,y) for(reg auto x:y)
#define ff fflush(stdout)
#define mt(x,y) memset(x,y,sizeof(x))
#define idg isdigit
#define fp(s) string ssss=s;freopen((ssss+".in").c_str(),"r",stdin);freopen((ssss+".out").c_str(),"w",stdout);
#define sstr stringstream 
#define all(x) x.begin(),x.end()
#define mcy(a,b) memcpy(a,b,sizeof(b))
using namespace std;
const int N=2e5+5;
vector<int>g[N],dfn(1,0);
bool vis[N];
int siz[N],mx[N];
inl void dfs(int u,int &rt,int n){
    vis[u]=siz[u]=1;
    at(v,g[u])
        if(!vis[v]){
            dfs(v,rt,n);
            siz[u]+=siz[v];
            mx[u]=max(mx[u],siz[v]);
        }
    mx[u]=max(mx[u],n-siz[u]);
    if(mx[u]<=n>>1) rt=u;
    vis[u]=0;
}
inl void dfs2(int u){
    vis[u]=1;
    dfn.pb(u);
    at(v,g[u])
        if(!vis[v]) dfs2(v);
    vis[u]=0;
}
signed main(){
    fst;
    reg int n,rt=0;
    cin>>n;
    rep(i,2,n){
        reg int u,v;
        cin>>u>>v;
        g[u].pb(v);
        g[v].pb(u);
    }
    dfs(1,rt,n);
    dfs2(rt);
    if(n&1)
        rep(i,2,(n>>1)+1) cout<<dfn[i]<<' '<<dfn[i+(n>>1)]<<endl;
    else rep(i,1,n>>1) cout<<dfn[i]<<' '<<dfn[i+(n>>1)]<<endl;
    return 0;
}