http://acm.hdu.edu.cn/showproblem.php?pid=6060 传送门
题目大意： 有一棵树T,n个点，n-1条边；将2,3,4,5,6，… n分到k个集合里面S1，S2，S3，… Sk；集合可以是空集，并且任意两个集合之间没有相同的点；定义一个函数f(S)=f({1}USi)为集合S中的最小斯坦纳树，即为每个集合中所有点加编号为1的节点相互连接所经过的边的权值之和，求k个点集权值最大的和； 如：对于Si={3,4},f(S)=f({1}U{3，4})的值为点1点2再到点3的值，加上点1到点2再到4的值之和；
解题思路：首先要知道，题目中所给的树就是一颗最小生成树，然后求f(S)=f（{1}USi）; 用题目给的样例来解释一下： k=4，要求把2-5分到4个集合里面，当然有些集合可以是空集 1.没有空集的时候，S1={2},S2={3},S3={4},S4={5}; f(S1)=f({1}U{2})=3; f(S2)=f({1}U{3})=7; f(S3)=f({1}U{4})=8; f(S4)=f({1}U{5})=9; res=f(S1)+f(S2)+f(S3)+f(S4)=27; 2.有1个空集，{2,3},{4},{5},{空集}，res=24，其余两种相同
3.有2个空集，{2,3,4},{5},{空集},{空集}，res=21，还有两种情况res值相同
4.有3个空集，{2,3,4,5},{空集},{空集},{空集}，res=18； 由上可知，空集的存在只会使得res变小，题目要求求最大res,所以就应该把2-n分到的k个集合中，并且集合里面没有空集的存在
求最大的res，而res是由边权加起来的，也就是说我们加上的边越多，res越大，所以应该尽量使得每条边都应该被走到； 如上图：考虑边A-C所做的贡献，目的使得A-C边被走的多一些，所以应该使得C点或者C点的子节点属于集合中，那么边A-C就会被走过；并且应该尽量使得C点或者C点的子节点分布于更多的集合中；设C点和C点的子节点数为sum;
/*若是 sum<k,这个时候C点和C点的子节点最多能分到sum个集合里面，A-C边最多被走过sum次 若是 sum>k,这个时候C点和C点的子节点最多能分到k个集合里面,A-C边最多被走过k次*/ #include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; typedef long long LL; const int maxn=1e7+10; typedef long long LL; int n,k,tot; int head[maxn],siz[maxn]; int w[maxn]; struct { int from,to,val,next; } G[maxn*2]; void add_edge(int from,int to,int val) { G[tot].from=from; G[tot].to=to; G[tot].val=val; G[tot].next=head[from]; head[from]=tot; tot++; } void dfs(int x,int father_x) { siz[x]=1; for(int i=head[x]; i!=-1; i=G[i].next) { int to=G[i].to; if(to==father_x) continue; w[to]=G[i].val; dfs(to,x); siz[x]+=siz[to]; } } int main() { int a,b,c; while(~scanf("%d%d",&n,&k)) { memset(head,-1,sizeof(head)); memset(siz,0,sizeof(siz)); memset(w,0,sizeof(w)); tot=0; for(int i=1; i<=n-1; i++) ///n-1条边 { scanf("%d%d%d",&a,&b,&c); add_edge(a,b,c); } dfs(1,-1); LL ans=0; for(int i=1; i<=n; i++) ans+=(LL)w[i]*min(k,siz[i]); printf("%lld\n",ans); } }