洛谷1131 [ZJOI2007]时态同步

日推水题系列。

对于每一个子树，每个叶节点对答案的贡献就是 根到所有叶节点距离的最大值 $dismax$ 减去 根到这个叶节点的距离 $dis[x]$。直接dfs即可。

注意要开long long，我又被坑了一次。

struct Edge{
    ll next,to,w;
} edge[1000005];
ll head[500005],cnt,n,m,s,a,b,c,dis[500005],ans;

inline void add(ll u,ll v,ll w)
{
    edge[++cnt].to=v;
    edge[cnt].w=w;
    edge[cnt].next=head[u];
    head[u]=cnt;
}

void dfs(ll x,ll f)
{
    ll siz=0;
    for (ll i=head[x];i;i=edge[i].next)
    {
        ll y=edge[i].to,w=edge[i].w;
        if (y==f) continue;
        dfs(y,x);
        if (dis[y]+w>dis[x])
        {
            ans+=siz*(dis[y]+w-dis[x]);
            dis[x]=dis[y]+w;
        }
        else ans+=dis[x]-dis[y]-w;
        siz++;
    }
    return;
}

int main()
{
    n=read(); s=read();
    for (ll i=1;i<n;i++)
    {
        a=read(); b=read(); c=read();
        add(a,b,c);
        add(b,a,c);
    }
    dfs(s,0);
    printf("%lld",ans);
    return 0;
}