lp2052 NOI2011 道路修建

作为一道NOI的题，它一度令我以为它是2001的。
不曾想，NOI竟然有这么水的题。
我一开始以为自己的写法错了。
但是…
唉，反正就是计算子树大小就对了。
另：存树的时候绝·对·不·可·以「u>v?u^=v^=u^=v:0」！！！这样会导致错误。反例：1->3,3->2。NOIP因为这个丢了很多分。

#include<iostream>
#include<cstdio>
#include<cmath>

struct ee{
    int v;
    int w;
    int nxt;
}e[2000005];
int h[1000005],et=0;
inline void add(int u,int v,int w){
    e[++et]=(ee){v,w,h[u]};
    h[u]=et;
}

int n,in[1000005];
int f[10000005];
bool vis[1000005];
long long ans=0;
inline void dfs(int X){
    for(int i=h[X];i;i=e[i].nxt){
        if(vis[e[i].v]==1){
            continue;
        }
        vis[e[i].v]=1;
        dfs(e[i].v);
        ans+=1LL*e[i].w*(std::abs(((f[e[i].v]<<1)-n)));
        f[X]+=f[e[i].v];
    }
    ++f[X];
}


void init(){
    scanf("%d",&n);
    int u,v,w;
    for(int i=1;i<n;++i){
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);
        add(v,u,w);
    }
    vis[1]=1;
    dfs(1);
    printf("%lld",ans);
}

int main(){
    init();
    return 0;
}