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 ;
}
05-06 03:42