官方题解

题目大意

有一颗 $n$ 个结点的树，定义一个结点的路径价值为 $f(x) = \sum_{i=1}^{n} (w_i \times d(x, i))$ ，求整棵树的最小路径价值。

解题思路

考虑计算所有结点的路径价值，取最小值即可得到答案。

以上实现方法很容易想到换根DP，设 $sum_i$ 表示子树 $i$ 的权值和，即

$$sum_i = \sum_{j=subtree_i} (w_j)$$

并记录以 $1$ 为根节点的路径价值 $f(1)$ 。

接下来考虑换根，假设当前结点为 $u$ ，父结点为 $fa$ ，那么 $f(u)=f(fa)+sum_1-2\times sum_u$

参考代码

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll N = 200010;

ll n;
vector<ll>v[N];
ll c[N];
ll sum[N];
ll tot;
ll ans;

ll dfs(ll u,ll fa,ll dep){
    sum[u]=c[u];
    tot+=c[u]*dep;
    for(auto x:v[u]){
        if(x==fa) continue;
        sum[u]+=dfs(x,u,dep+1);
    }
    return sum[u];
}

void dfs1(ll u,ll fa,ll now){
    ans=min(ans,now);
    for(auto x:v[u]){
        if(x==fa) continue;

        ll res=now+sum[1]-2*sum[x];
        dfs1(x,u,res);
    }
}

int main(){
    cin>>n;
    for(int i=1;i<n;i++){
        int a,b;cin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    for(int i=1;i<=n;i++) cin>>c[i];

    dfs(1,-1,0);

    ans=tot;
    dfs1(1,-1,tot);
    cout<<ans<<endl;
    return 0;
}