首页 > 代码库 > Codeforces 700B Connecting Universities(树形DP)
Codeforces 700B Connecting Universities(树形DP)
【题目链接】 http://codeforces.com/problemset/problem/700/B
【题目大意】
给出 一棵n个节点的树, 现在在这棵树上选取2*k个点,两两配对,使得其配对的两点间距离的和最大。
【题解】
求出树的加权重心,那么答案就是每个点到加权重心的距离之和,但是实际上,并不需要求出加权重心,观察树边和其两边的询问节点,可以发现一个优美的性质,每条边对答案的贡献值为min(左边的点数,右边的点数),因此,树规计算每条边的贡献值,累加和就是答案。
【代码】
#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;}
Codeforces 700B Connecting Universities(树形DP)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。