【bzoj1060】[ZJOI2007]时态同步

2015.05.28 18:10 Thu | 16次阅读 | 旧日oi | 固定链接 | 源码

题目大意:给定一颗有边权的树,每次可以把一条边的边权+1,求最少需要多少次能让根到叶子节点的距离都相同。
题解:
两边dfs解决,或许一遍也可以,反正大水题……
但是!!!这题数据有问题,有的地方应该加long long,但事实上你加了就会wa……

我的程序

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#define ll long long
#define N 500005
using namespace std;
int n,root;
struct edge{
    int to,next;
    int val;
}e[N<<1];
int h[N],tp;
void ae(int u,int v,int w)
{
    e[++tp].to=v;
    e[tp].next=h[u];
    e[tp].val=w;
    h[u]=tp;
}
int dis[N];
ll ans,mx;
void dfs1(int u,int f)
{
    for(int v,i=h[u];e[i].to;i=e[i].next)
    if((v=e[i].to)!=f)
    {
        dfs1(v,u);
        dis[u]=max(dis[u],dis[v]+e[i].val);
    }
}
void dfs2(int u,int f,int d)
{
    for(int v,i=h[u];e[i].to;i=e[i].next)
    if((v=e[i].to)!=f)
    {
        int tmp=(mx-d-e[i].val-dis[v]);
        ans+=tmp;dfs2(v,u,d+e[i].val+tmp);
    }
}
int main()
{
    scanf("%d%d",&n,&root);
    for(int u,v,w,i=1;i<n;i++)  
    {
        scanf("%d%d%d",&u,&v,&w);
        ae(u,v,w);ae(v,u,w);
    }
    dfs1(root,0);mx=dis[root];
    dfs2(root,0,0ll);
    cout<<ans<<endl;
}```