HDU

Bryce1010模板

http://acm.hdu.edu.cn/showproblem.php?pid=6060

#include<bits/stdc++.h>

using namespace std;
#define ll long long
const ll MAXN=1e6+10;
ll n,k;
struct Edge
{
    ll to,cost;
    Edge(){}
    Edge(ll a,ll b):to(a),cost(b){}
};


vector<Edge>G[MAXN];

ll son[MAXN];
ll ans=0;

void init()
{
    ans=0;
    for(ll i=0;i<MAXN;i++)
    {
        G[i].clear();
    }
    memset(son,0,sizeof(son));
}


void dfs(ll u,ll fa)
{
    son[u]++;
    for(ll i=0;i<G[u].size();i++)
    {
        Edge e=G[u][i];
        if(e.to==fa)continue;
        dfs(e.to,u);
        son[u]+=son[e.to];
        ans+=min(son[e.to],k)*e.cost;
    }

}
void solve()
{
    dfs(1,-1);
    printf("%lld
",ans);
}


int main()
{

    while(scanf("%lld%lld",&n,&k)!=EOF)
    {
        init();
        ll a,b,c;
        for(ll i=0;i<n-1;i++)
        {
            scanf("%lld%lld%lld",&a,&b,&c);
            G[a].push_back(Edge(b,c));
            G[b].push_back(Edge(a,c));
        }
        solve();
    }
    return 0;
}