前言

我觉得只要给我时间到这题就随便过,因为我对于换根还是没那么熟悉...
读这题的时候就半小时了,知道写不完了,就没写了..今天写了,debug也差不多..
我代码真的容易出bug...下次一定提前开题,签到题留给队友写.感觉就是cf2100到2200的换根dp.

思路

好像就是一些式子推一下,首先算一个比较大的,表示子树的答案,当然没什么作用,就是算出的.
然后手推几个式子就出来了..反正换根就是考虑怎么从父亲节点转移到子节点嘛..
我觉得变量名很好看.

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
struct node{
    ll to,val;
};
vector<node>g[N];
ll ans[N],f[N],dis[N],val[N],sum[N],sz[N],Sum,n;
void dfs(int u,int fa)
{
    sz[u]=1;sum[u]=val[u];
    for(auto v:g[u])
    {
        if(v.to==fa)    continue;
        dfs(v.to,u);
        sz[u]+=sz[v.to];
        sum[u]+=sum[v.to];
        dis[u]+=dis[v.to]+sz[v.to]*v.val;
        f[u]+=f[v.to]+v.val*sum[v.to]-dis[v.to]*val[v.to]+(dis[v.to]+sz[v.to]*v.val)*val[u];
    }
}

void DFS(int u,int fa)
{
    if(fa==-1)
    {
        ans[u]=f[u];Sum=sum[u];
    }
    for(auto v:g[u])
    {
        if(v.to==fa)   continue;
        dis[v.to]=dis[u]+((n-2ll*sz[v.to]))*v.val;
        ans[v.to]=ans[u]-(dis[u]*val[u])+(Sum-2ll*sum[v.to])*v.val+dis[v.to]*val[v.to];
        DFS(v.to,u);
    }
}

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>val[i];
    for(int i=1;i<n;i++)
    {
        ll u,v,w;
        cin>>u>>v>>w;
        g[u].push_back({v,w});
        g[v].push_back({u,w});
    }
    dfs(1,1);
    DFS(1,-1);
    for(int i=1;i<=n;i++)   cout<<ans[i]<<'\n';
    return 0;
}