Codeforces 700B Connecting Universities

题面在这里

​

对于每条边\((u,v)\)，对答案的贡献是两边特殊点少的那个

​

示例程序：

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;

const int maxn=200005,maxe=400005;
int n,K,s[maxn]; ll ans;
int son[maxe],nxt[maxe],lnk[maxn],tot;
inline void add(int x,int y){
	son[++tot]=y;nxt[tot]=lnk[x];lnk[x]=tot;
}
void dfs(int x,int fa){
	for (int j=lnk[x];j;j=nxt[j])
	 if (son[j]!=fa) dfs(son[j],x),s[x]+=s[son[j]],ans+=min(s[son[j]],2*K-s[son[j]]);
}
int main(){
	scanf("%d%d",&n,&K);
	for (int i=1,x;i<=2*K;i++) scanf("%d",&x),s[x]++;
	for (int i=1,x,y;i<n;i++) scanf("%d%d",&x,&y),add(x,y),add(y,x);
	dfs(1,1);
	printf("%lld",ans);
	return 0;
}