[EZOJ3384] 配对

有一棵树，树上有 n 个点，每条边上有一个非负边权。
在这 n 个点中有 k 个特殊点，其中 k 为偶数。定义两个点的距离为它们在树上的简单路径上的边权之和。你需要将这 k 个点配成$\frac k2$个互不相交的对，并最大化每一对点的距离之和。

Solution:
可以先考虑最大价值是多少。
对于一条边，如果两侧分别有a,b个点，那么它的贡献最多为min(a,b)乘上权值。
这个上限是可以取满的。
对原图建虚数，并找出重心。
这时重心的每个儿子的大小都小于$\frac k2$，只需要保证每次匹配的点来自不同子树的点，就可以保证对于每条边连接的两个子树，小的子树的点总是匹配大的子树的点。
就满足条件了。
又是虚树又是重心……好麻烦啊，匹配还要仔细处理。
会发现其实虚数不用建出来，可以在原树上处理，只要重心是虚树的就行。
从重心开始dfs，令第i个特殊点的dfs序为$p_ i$,发现$p_ i$和$p_ {i+\frac k2}$直接匹配是合法的。
子树大小不会大于$\frac k2$，所以这两个点不会在一颗子树中。

现在直接从1号点开始dfs。会发现每个子树代表的dfs序区间只是按顺序转了一下，1号点所在的区间被分成了两半。
原来的匹配刚好是$\frac k2$为循环节，可以看成环上的匹配，发现不会有任何影响。

code:

#include <iostream>
#include <cstdio>
#include <cstring>
const int N=1e5+5;
int n,m,pt_ans,ans[N];

namespace IO{
	const int SIZE=1<<16;
	char ibuf[SIZE],*ih,*it;
	inline char get_c(){
		if(ih==it){
			it=(ih=ibuf)+fread(ibuf,1,SIZE,stdin);
			if(ih==it) return EOF;
		}
		return *ih++;
	}
	template <class T> inline T nxi(){
		T x=0;
		char c;
		while((c=getchar())>'9'||c<'0');
		while(x=x*10-48+c,(c=getchar())>='0'&&c<='9');
		return x;
	}
}
using IO::nxi;
using IO::get_c;

namespace G{
	int cnt,fir[N];
	bool vis[N];
	struct edge{
		int to,nx;
	}eg[N<<1];

	inline void add(const int a,const int b){
		eg[++cnt]=(edge){b,fir[a]};
		fir[a]=cnt;
	}

	inline void dfs(const int x,const int fa){
		if(vis[x]) ans[++pt_ans]=x;
		for(int i=fir[x]; i; i=eg[i].nx){
			const int y=eg[i].to;
			if(y!=fa) dfs(y,x);
		}
	}
}

int main(){
	n=nxi<int>(),m=nxi<int>();
	for(int i=1; i<n; ++i){
		int a=nxi<int>(),b=nxi<int>();
		nxi<int>();
		G::add(a,b);
		G::add(b,a);
	}
	for(int i=1; i<=m; ++i){
		G::vis[nxi<int>()]=1;
	}
	G::dfs(1,1);
	for(int i=1,j=i+(m>>1); j<=m; ++i,++j){
		printf("%d %d\n",ans[i],ans[j]);
	}
	return 0;
}