BZOJ1060 [ZJOI2007]时态同步

2014.12.09 16:13 Tue| 2 visits oi_2015| 2015_刷题日常| Text

Solution

据说这题数据有问题,中间运算虽然会爆,但是只能用 int ,只有答案需要开 long long 。知道了这一坑点,此题就是一道最简单的树上 DP QAQ,简单YY一下就可以得出解法咯!

就是因为交错成了这道题,AC率又下降了 T_T

Code

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

int n,root,cost[N],fa[N]; long long ans;
int head[N],next[N*2],to[N*2],val[N*2],cnt;

inline 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)
{
    for(int i=head[x],y;i;i=next[i])
        if((y=to[i])!=fa[x])
            fa[y]=x, dfs(y), cost[x]=max(cost[x],cost[y]+val[i]);
    for(int i=head[x],y;i;i=next[i])
        if((y=to[i])!=fa[x])
            ans+=cost[x]-cost[y]-val[i];
}

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