BZOJ2435 道路修建

2014.12.22 12:18 Mon| 4 visits oi_2015| 2015_刷题日常| Text

Solution

或许是最简单不过的树形DP吧。据说BFS会挂,但是实际上DFS怎么搜都是没问题的。

//pengzhou坑得我差一点点就写BFS了……切忌听信谣言

Code

#include <bits/stdc++.h>
using namespace std;

#define N 1000005

bool vis[N];
int n,size[N];
long long ans;
int head[N],next[N*2],to[N*2],val[N*2],cnt;


void add(int x,int y,int z)
{
    to[++cnt]=y; val[cnt]=z;
    next[cnt]=head[x]; head[x]=cnt;
}

inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

void dfs(int x)
{
    size[x]=1; vis[x]=true;
    for(int y,i=head[x];i;i=next[i])
        if(!vis[y=to[i]])
            dfs(y=to[i]), ans+=(long long)val[i]*abs(n-size[y]-size[y]),
            size[x]+=size[y];
}

int main()
{
    cin>>n;
    for(int x,y,z,i=1;i<n;i++)
        x=read(), y=read(), z=read(),
        add(x,y,z), add(y,x,z);
    dfs(1);
    cout<<ans<<endl;
}