codeforces 700B_codeforces - 700b

#include<bits/stdc++.h>
typedef long long LL;
using namespace std;
class Solution{
	vector<vector<int> > tr;
	vector<int> vi,cnt;
	int n,m;
	LL ret;
public:
	void init(){
		cin>>n>>m;
		tr = vector<vector<int> >(n+1);
		vi = cnt = vector<int> (n+1,0);
		for(int i=0;i<2*m;i++){
			int x;
			cin>>x;
			vi[x] = 1;
		}
		for(int i=1;i<n;i++){
			int x,y;
			cin>>x>>y;
			tr[x].push_back(y);
			tr[y].push_back(x);
		}
	}
	void dfs(int st,int f){
		cnt[st] = vi[st];
		for(int i=0;i<(int)tr[st].size();i++){
			int to = tr[st][i];
			if(to==f) continue;
			dfs(to,st);
			ret += min(cnt[to],2*m-cnt[to]);
			cnt[st]+=cnt[to];
		}
	}
	void solve(){
		ret = 0;
		dfs(1,-1);
		cout<<ret<<endl;
	}
};
int main(){
	ios_base::sync_with_stdio(0);
	Solution * sol = new Solution();
	sol->init();
	sol->solve();
	return 0;
}

题意：给出一棵树上的2*k个节点，给他们配对，使得他们之间的距离和最大。

题解：可以证明任何一条边最多被这个边左右两棵子树中指定节点数的较小值的边经过。知道这个性质之后就很简单了，枚举边、统计。