树形dp Codeforces Round #364 (Div. 1)B

http://codeforces.com/problemset/problem/700/B

题目大意：给你一棵树，给你k个树上的点对。找到k/2个点对，使它在树上的距离最远。问，最大距离是多少？

思路：我们可以把树上的这个分成两个集合，然后两边的点的数目相等。符合这个条件的就是树的重心，所以我们只需要找到树的中心就行啦。

//看看会不会爆int!数组会不会少了一维！

//取物问题一定要小心先手胜利的条件

#include <bits/stdc++.h>

using namespace std;

#pragma comment(linker,"/STACK:102400000,102400000")

#define LL long long

#define ALL(a) a.begin(), a.end()

#define pb push_back

#define mk make_pair

#define fi first

#define se second

#define haha printf("haha\n")

/*

题目大意：

给你一棵树，给你k个树上的点对。找到k/2个点对，使它在树上的距离最远。

问，最大距离是多少？

*/

const int maxn =  + ;

int n, k;

vector<int> G[maxn];

bool vis[maxn];

int dp_cnt[maxn];

int dfs_cnt(int u, int fa){

    int cnt = vis[u];

    for (int i = ; i < G[u].size(); i++){

        int v = G[u][i];

        if (v == fa) continue;

        cnt += dfs_cnt(v, u);

    }

    return dp_cnt[u] = cnt;

}

void dfs_ce(int u, int fa, int &ce, int &maxcnt, int treesize){

    int tmp = treesize - dp_cnt[u];

    for (int i = ; i < G[u].size(); i++){

        int v = G[u][i];

        if (v == fa) continue;

        tmp = max(tmp, dp_cnt[v]);

        dfs_ce(v, u, ce, maxcnt, treesize);

    }

    if (maxcnt > tmp){

        maxcnt = tmp; ce = u;

    }

}

LL ans;

void dfs(int u, int fa, int len){

    if (vis[u]) {

        ans = 1LL * len + ans;

    }

    for (int i = ; i < G[u].size(); i++){

        int v = G[u][i];

        if (v == fa) continue;

        dfs(v, u, len + );

    }

}

int main(){

    scanf("%d%d", &n, &k);

    for (int i = ; i <= k * ; i++){

        int u; scanf("%d", &u);

        vis[u] = true;

    }

    for (int i = ; i < n; i++){

        int u, v; scanf("%d%d", &u, &v);

        G[u].pb(v); G[v].pb(u);

    }

    int treesize = dfs_cnt(, -);

    int cetroid, maxcnt = maxn;

    dfs_ce(, -, cetroid, maxcnt, treesize);

    dfs(cetroid, -, );

    printf("%lld\n", ans);

    return ;

}