本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 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;
}