<span>codeforces 700B Connecting Universities</span>
题意：
给你一棵树，边权均为1，上面有2K个点为学校
让你将学校配对，配对的学校需要修路连接
问修的路最长为多少
思路：
每条边计算最大价值
即这条边两端学校中较小的那个数量
因为最大利用这条边就要把两端的学校配对
较少的那端的学校全都配对过去，就全都走了这条路
然后把每个边的价值加起来就是答案
注意用LL
/* *********************************************** Author :devil ************************************************ */ #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include <string> #include <cmath> #include <stdlib.h> using namespace std; typedef long long LL; const int inf=0x3f3f3f3f; const int mod=1e9+7; const int N=2e5+10; int n,k,sum[N]; LL dp[N]; vector<int>eg[N]; void dfs(int u,int pre) { dp[u]=0; for(int i=0;i<eg[u].size();i++) { int v=eg[u][i]; if(v==pre) continue; dfs(v,u); sum[u]+=sum[v]; dp[u]+=dp[v]+min(sum[v],k-sum[v]); } } int main() { //freopen("in.txt","r",stdin); int x,y; scanf("%d%d",&n,&k); k<<=1; for(int i=0;i<k;i++) { scanf("%d",&x); sum[x]=1; } for(int i=1;i<n;i++) { scanf("%d%d",&x,&y); eg[x].push_back(y); eg[y].push_back(x); } dfs(1,-1); printf("%I64d\n",dp[1]); return 0; }
农夫山泉工作强度 11人发布