BZOJ_2435_[Noi2011]道路修建_dfs

BZOJ_2435_[Noi2011]道路修建_dfs

题意：

http://www.lydsy.com/JudgeOnline/problem.php?id=2435

分析：

dfs搞定。

我怕爆栈写了非递归dfs。

其实bfs两遍也可以做。

代码：

#include <stdio.h>

int head[1000001],to[2000010],nxt[2000010],cnt,n,val[2000010];

int fa[1000001],siz[1000001];

__attribute__((optimize("-O2")))inline char nc(){

    static char buf[100000],*p1=buf,*p2=buf;

    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;

}

__attribute__((optimize("-O2")))inline int read(){

    char ch=nc();int sum=0;

    while(!(ch>='0'&&ch<='9'))ch=nc();

    while(ch>='0'&&ch<='9')sum=(sum<<3)+(sum<<1)+ch-48,ch=nc();

    return sum;

}

__attribute__((optimize("-O2")))int main(){

    n=read();

    register int i,x,y,z;

    for(i=1;i<n;i++){

        x=read(),y=read(),val[i]=read();siz[i]=1;

        to[++cnt]=y;nxt[cnt]=head[x];head[x]=cnt;

        to[++cnt]=x;nxt[cnt]=head[y];head[y]=cnt;

    }

    siz[n]=1;x=1;

    while(x)

    {

        int f=0;

        for(i=head[x];i;i=nxt[i])

        {

            if(to[i]==fa[x])continue;

            f=1;

            fa[to[i]]=x;

            head[x]=nxt[i];

            x=to[i];

            break;

        }

        if(f==0)siz[fa[x]]+=siz[x],x=fa[x];

    }

    long long ans=0;

    for(i=1;i<2*n-2;i+=2){

        x=to[i],y=to[i+1],z=val[i+1>>1];

        if(fa[y]==x){int t=x;x=y;y=t;}

        ans+=1ll*z*(n-siz[x]-siz[x]<0?siz[x]+siz[x]-n:n-siz[x]-siz[x]);

    }

    printf("%lld\n",ans);

}