给定树上2k个点两两配对，求距离和最大值。1e6
首先这种1e6的树上的题，一般都是$O(n)$的，所以两个思路，要么是DP，要么是贪心扫一遍。
比如说这个题，首先就是对于每对点，我尽量把lca往上提，这样就能保证答案最大值，然后每往上抬一个，只要是边他的贡献就是1,所以我们可以dfs，策略是能往上抬就往上抬，带着一堆点伸出的边，如果能外边有足够配对的点，那就往上抬，如果没有，我就两两就地配对。
然后就是比较帅气的AC了。
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=100010;
int fr[N],fa[N],f[N],size[N],dep[N],a[N],b[N],p[N],n,k,s,tt,tot;
long long ans;
bool v[N];
struct node{int to,pr;}mo[N*2];
inline int rd()
{
int s=0,w=1;
char cc=getchar();
for(;cc<'0'||cc>'9';cc=getchar()) if(cc=='-') w=-1;
for(;cc>='0'&&cc<='9';cc=getchar()) s=(s<<3)+(s<<1)+cc-'0';
return s*w;
}
void add(int x,int y)
{
mo[++tt]=(node){y,fr[x]};
fr[x]=tt;
}
void dfs(int x)
{
for(int i=fr[x];i;i=mo[i].pr)
{
int to=mo[i].to;
if(to==fa[x])continue;
fa[to]=x;
dfs(to);
f[x]+=f[to]+min(size[to],2*k-size[to]);
size[x]+=size[to];
}
//cout<<x<<" "<<size[x]<<endl;
}
int main()
{
n=rd(),k=rd(),s=rd();
for(int i=1;i<=k*2;i++) p[i]=rd(),size[p[i]]=1;
for(int i=1;i<n;i++)
{
int x=rd(),y=rd();
add(x,y);add(y,x);
}
dfs(1);
printf("%d\n",f[1]);
}
/*
g++ 2.cpp -o 2 -O2
./2
7 2 0
1 5 6 2
1 3
3 2
4 5
3 7
4 3
4 6
*/