题目概述

一棵 $n$ 个点的树，给出 $2k$ 个关键点，现在要把这 $2k$ 个点组成 $k$ 对，每对的贡献为点之间的距离，求最大贡献。

解题报告

完全想不到……考虑每条边的贡献，很明显最大是第一个点子树中的关键点个数和第二个点子树中关键点的个数的最小值。但是每条边都能取到这个最大值吗？感性理解一下，用这样的方法进行构造，肯定是能够构造出来的。

示例程序

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=200000;

int n,K,cnt[maxn+5],X[maxn+5],Y[maxn+5];LL ans;
int E,lnk[maxn+5],son[(maxn<<1)+5],nxt[(maxn<<1)+5];

#define Add(x,y) (son[++E]=(y),nxt[E]=lnk[x],lnk[x]=E)
void Dfs(int x,int pre=-1){
    for (int j=lnk[x];j;j=nxt[j])
        if (son[j]!=pre) Dfs(son[j],x),cnt[x]+=cnt[son[j]];
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d%d",&n,&K);for (int i=1,x;i<=(K<<1);i++) scanf("%d",&x),cnt[x]++;
    for (int i=1,x,y;i<n;i++) scanf("%d%d",&X[i],&Y[i]),Add(X[i],Y[i]),Add(Y[i],X[i]);Dfs(1);
    for (int i=1,MIN;i<n;i++) MIN=min(cnt[X[i]],cnt[Y[i]]),ans+=min(MIN,(K<<1)-MIN);
    return printf("%lld\n",ans),0;
}