题目链接

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+20;
using ll= long long;
typedef pair<int,int>PII;
vector<int>g[N]; 
int n,m;
ll c[N];
ll dp[N];// dp[x] :答案 f(x) 
ll sum[N];//sum[i]以i为根的子树权值和 
void dfs(int u,int f,ll deep)
{
    dp[1]+=deep*c[u];
    sum[u]=c[u]; 
    for(auto i:g[u])
    {
        if(i==f) continue;
        dfs(i,u,deep+1);
        sum[u]+=sum[i]; 
     } 
}
//sum[1]：相当于所有节点权值和 
void ddfs(int u,int f)
{
    for(auto i:g[u])
    {
        if(i==f) continue;
        dp[i]=dp[u]+sum[1]-2*sum[i];
        ddfs(i,u); 
    }
}
void solved()
{
    cin>>n;
    for(int i=1;i<n;i++)
    {
        int a,b;cin>>a>>b;
        g[a].push_back(b);
        g[b].push_back(a); 
    }
    for(int i=1;i<=n;i++) cin>>c[i];
    dfs(1,0,0); //以1为根节点，递归树,求出根dp[1]，以及sum权值
    ddfs(1,0);
    ll ans=dp[1];
    for(int i=1;i<=n;i++) ans=min(ans,dp[i]);
    cout<<ans<<'\n';
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t=1;
    while(t--)
    solved();
}