给定树上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 */