Codeforces 700B Connecting Universities(树形DP)
【题目链接】 http://codeforces.com/problemset/problem/700/B
【题目大意】
给出 一棵n个节点的树, 现在在这棵树上选取2*k个点,两两配对,使得其配对的两点间距离的和最大。
【题解】
求出树的加权重心,那么答案就是每个点到加权重心的距离之和,但是实际上,并不需要求出加权重心,观察树边和其两边的询问节点,可以发现一个优美的性质,每条边对答案的贡献值为min(左边的点数,右边的点数),因此,树规计算每条边的贡献值,累加和就是答案。
【代码】
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | # include <cstdio> # include <vector> # include <algorithm> using namespace std; const int N= 200005 ; int n,k,s[N],x,y; long long ans= 0 ; vector< int > g[N]; void dfs( int x, int pre){ for ( int i= 0 ;i<g[x].size();i++){ if (g[x][i]==pre) continue ; dfs(g[x][i],x); s[x]+=s[g[x][i]]; ans+=min(s[g[x][i]], 2 *k-s[g[x][i]]); } } int main(){ scanf( "%d%d" ,&n,&k); for ( int i= 1 ;i<= 2 *k;i++)scanf( "%d" ,&x),s[x]++; for ( int i= 1 ;i<n;i++){ scanf( "%d%d" ,&x,&y); g[x].push_back(y);g[y].push_back(x); }dfs( 1 ,- 1 ); return printf( "%I64d" ,ans), 0 ; } |