hdu 6060 RXD and dividing(dfs)

题目链接：hdu 6060 RXD and dividing

题意：

给你一棵树，让你将树的节点划分为k个集合，每个集合都会包括1这个节点，每个集合的价值为这个点集的斯坦纳树的价值。

题解：

比赛的时候看错题啊！！！！！，什么鬼斯坦纳树，结果是对于每个集合的点，选一些树上的边，恰好使这个集合的点连通就行了。

MD！！！

如果要分为k个集合，对于每一条边u->v，显然要让他尽可能的出现在每一个集合，但是这条边最多出现的次数又受到以v为根节点的子树大小（即size[v])限制，所以u->v这条边的贡献就是val(u->v)*min(k,size[v])。至于集合怎么分，只要将v这棵子树分为min(k,size[v])份就行了，每份标一个号。然后将所有标号一样的划分为一个集合就行了。

#include<bits/stdc++.h>
#define F(i,a,b) for(int i=a;i<=b;i++)
using namespace std;

const int N=1e6+7;
int n,k,g[N],ed,nxt[N*2],v[N*2],w[N*2],sz[N];
long long ans;
inline void adg(int x,int y,int z){v[++ed]=y,w[ed]=z,nxt[ed]=g[x],g[x]=ed;}

void dfs(int x,int fa,int val)
{
    sz[x]=1;
    for(int i=g[x];i;i=nxt[i])if(v[i]!=fa)
        dfs(v[i],x,w[i]),sz[x]+=sz[v[i]];
    ans+=1ll*min(k,sz[x])*val;
}

int main()
{
    while(~scanf("%d%d",&n,&k))
    {
        F(i,1,n)g[i]=0;
        ed=0;ans=0;
        F(i,2,n)
        {
            int x,y,z;
            scanf("%d%d%d",&x,&y,&z);
            adg(x,y,z),adg(y,x,z);
        }
        dfs(1,0,0);
        printf("%lld
",ans);
    }
    return 0;
}