Description：

一棵带边权的树，有 $k$ 个特殊点。将这 $k$ 个点配成 $\frac k 2$ 个互不相交的对，并最大化每一对点的距离之和。

$1\leqslant n\leqslant 10^5$

Solution：

首先观察到结论就是最后所有的匹配一定经过一个点，否则的话一定可以通过交换一对匹配使得距离之和变大。

然后我们可以用类似点分治找重心的方法找到这 $k$ 个点的重心，这个点一定满足每一个子树中都有不超过 $\frac k 2$ 个关键点，我们要将这些点匹配起来，要求匹配的两个点不能来自同一棵子树，这个是一定能做到的，所以我们只要一个个匹配，如果还剩下就拆掉一些原来的匹配即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 100010

bool tag[MAXN];

struct edge

{

	int to,nxt,c;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b,int c)

{

	e[++edgenum] = (edge){b,lin[a],c};lin[a] = edgenum;

	e[++edgenum] = (edge){a,lin[b],c};lin[b] = edgenum;

	return; 

}

int root,siz[MAXN],d[MAXN];

void getroot(int k,int fa)

{

	siz[k] = tag[k];d[k] = 0;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to != fa)

		{

			getroot(e[i].to,k);

			siz[k] += siz[e[i].to];

			d[k] = max(d[k],siz[e[i].to]);

		}

	}

	d[k] = max(d[k],m - siz[k]);

	if(d[k] < d[root])root = k;

	return;

}

int ans[MAXN][2],anscnt = 0;

int stack[MAXN],top = 0;

int t[MAXN];

void dfs(int k,int fa)

{

	if(tag[k])t[++t[0]] = k;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to == fa)continue;

		dfs(e[i].to,k);

	}

	return;

}

void calc(int k)

{

	if(tag[k])stack[++top] = k;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		t[0] = 0;

		dfs(e[i].to,k);

		int x;

		for(x = 1;x <= t[0] && top > 0;++x)

		{

			++anscnt;

			ans[anscnt][0] = stack[top--];

			ans[anscnt][1] = t[x];

		}

		for(;x <= t[0];++x)stack[++top] = t[x];

	}

	if(top != 0)

	{

		for(int cur = 1;top > 0;++cur)

		{

			++anscnt;

			ans[anscnt][0] = stack[top--];

			ans[anscnt][1] = ans[cur][1];

			ans[cur][1] = stack[top--];

		}

	}

	return;

}

int main()

{

	freopen("pair.in","r",stdin);

	freopen("pair.out","w",stdout);

	scanf("%d%d",&n,&m);

	int a,b,c;

	for(int i = 1;i < n;++i)

	{

		scanf("%d%d%d",&a,&b,&c);

		add(a,b,c);

	}

	for(int i = 1;i <= m;++i)

	{

		scanf("%d",&a);

		tag[a] = true;

	}

	root = 0;d[0] = 0x3f3f3f3f;

	getroot(1,0);

	calc(root);

	for(int i = 1;i <= m / 2;++i)

	{

		printf("%d %d\n",ans[i][0],ans[i][1]);

	}

	fclose(stdin);

	fclose(stdout);

	return 0;

}