【多校訓練】hdu 6060 RXD and dividing dfs

Problem Description RXD has a tree  T , with the size of  n . Each edge has a cost.

Define  f(S)  as the the cost of the minimal Steiner Tree of the set  S  on tree  T . 

he wants to divide  2,3,4,5,6,…n  into  k  parts  S1,S2,S3,…Sk ,

where  ⋃Si={2,3,…,n}  and for all different  i,j  , we can conclude that  Si⋂Sj=∅ . 

Then he calulates  res=∑ki=1f({1}⋃Si) .

He wants to maximize the  res .

1≤k≤n≤106

the cost of each edge∈[1,105]

Si  might be empty.

f(S)  means that you need to choose a couple of edges on the tree to make all the points in  S  connected, and you need to minimize the sum of the cost of these edges.  f(S)  is equal to the minimal cost 

Input There are several test cases, please keep reading until EOF.

For each test case, the first line consists of 2 integer  n,k , which means the number of the tree nodes , and  k  means the number of parts.

The next  n−1  lines consists of 2 integers,  a,b,c , means a tree edge  (a,b)  with cost  c .

It is guaranteed that the edges would form a tree.

There are 4 big test cases and 50 small test cases.

small test case means  n≤100 .  

Output For each test case, output an integer, which means the answer.  

Sample Input

5 4
1 2 3
2 3 4
2 4 5
2 5 6
        

Sample Output

27
        

題意：

有一顆n個節點的樹，現在将節點2-n分成k組，定義每組的的權值為該組内所有點加編号為1的節點互相連接配接所經過的邊的權值的和，求k組點集最大的和。

思路：

把1看成整棵樹的根. 問題相當于把2∼n2∼n每個點一個[1,k][1,k]的标号. 然後根據最小斯坦納樹的定義, (x,fax)(x,fa​x​​) 這條邊的貢獻是 x 子樹内不同标号的個數目difidif​i​​. 那麼顯然有difi≤min(k,szi)dif​i​​≤min(k,sz​i​​), szisz​i​​表示子樹大小. 可以通過構造讓所有difidif​i​​都取到最大值. 是以答案就是∑x=2nw[x][fax]∗min(szx,k)∑​x=2​n​​w[x][fa​x​​]∗min(sz​x​​,k) 時間複雜度O(n)O(n).

//
//  main.cpp
//  1005
//
//  Created by zc on 2017/8/21.
//  Copyright © 2017年 zc. All rights reserved.
//

#include <iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define ll long long
using namespace std;
const int N=1100000;
const int M=4400000;
int cnt,head[N],n,k;
ll ans;
struct node
{
    int next,v;
    ll c;
}e[M];

void init()
{
    memset(head,-1,sizeof(head));
    cnt=0;
}

void add(int u,int v,ll c)
{
    e[cnt].c=c;
    e[cnt].v=v;
    e[cnt].next=head[u];
    head[u]=cnt++;
}

int dfs(int t,int fa)
{
    int sum=1;
    for(int i=head[t];i+1;i=e[i].next)
    {
        int v=e[i].v;
        if(v==fa)   continue;
        int p=dfs(v,t);
        sum+=p;
        ans+=min(k,p)*e[i].c;
    }
    return sum;
}

int main(int argc, const char * argv[]) {
    while(~scanf("%d%d",&n,&k))
    {
        init();
        for(int i=0;i<n-1;i++)
        {
            int u,v;
            ll c;
            scanf("%d%d%lld",&u,&v,&c);
            add(u,v,c);
            add(v,u,c);
        }
        ans=0;
        dfs(1,-1);
        printf("%lld\n",ans);
    }
}