codeforces 701 E. Connecting Universities（树+ 边的贡献）

题目链接：http://codeforces.com/contest/701/problem/E

题意：有n个城市构成一棵树，一个城市最多有一个学校，这n个城市一共2*k个学校，要对这2*k个学校进行连边，使得所有连出来的边的和最大，每条边边权为1.

题解：这题有一个巧妙的解法，可以记录一下每一条边的贡献（所谓贡献就是有多少对点连线会经过这条边）

也就是记录一下这条边左端点以左的所有需要连的点x和右端点的数目就是2*k-x。然后边的贡献就是两者取

最小。这样dfs一遍所有的边就行了。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
using namespace std;
typedef long long ll;
const int M = 2e5 + 10;
bool Is[M];
vector<int>vc[M];
ll ans , son[M];
int n , k , x;
void dfs(int pos , int pre) {
    int len = vc[pos].size();
    if(Is[pos]) son[pos] = 1;
    for(int i = 0 ; i < len ; i++) {
        int v = vc[pos][i];
        if(v != pre) {
            dfs(v , pos);
            son[pos] += son[v];
        }
    }
    ans += min(son[pos] , 2 * k - son[pos]);
}
int main() {
    scanf("%d%d" , &n , &k);
    for(int i = 1 ; i <= 2 * k ; i++) {
        scanf("%d" , &x);
        Is[x] = true;
    }
    int u , v;
    for(int i = 1 ; i < n ; i++) {
        scanf("%d%d" , &u , &v);
        vc[u].push_back(v);
        vc[v].push_back(u);
    }
    ans = 0;
    memset(son , 0 , sizeof(son));
    dfs(1 , -1);
    printf("%I64d
" , ans);
    return 0;
}