AT_abc409_e 题解

JHR100330 · 2025-06-09 08:42:38 · 题解

题目大意

给定一颗树与其点权、边权，从一个点 u 移动 1 至其相邻点 v 代价为边 (u,v) 的权值 w_{u,v}，求将所有点权变为 0 的最小代价。

题目分析

首先，显然，从一个点移动 1 至另一个点的最小代价是固定的，为其简单路径的边权总和，则只要不重复走边结果一定是最优的。

其次，我们发现从 u 移动 1 至 v 等价与从 v 移动 -1 至 u，则任选一点为根，使用树形动态规划，将所有点权移动到根节点即可。

状态转移方程：f_u = f_u + f_v。

答案累加：ans = ans + \lvert f_v \rvert * w_{u,v}。

可以说是板子题了。

Code

#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define PII pair<int, int>
#define PLL pair<ll, ll>

const ll inf = LONG_LONG_MAX, N = 100050;

ll n, u, v, c, ans = 0; 
ll arr[N]; 
vector<PII> e[N];

void dfs(ll now, ll fa){
    for(PII i : e[now]){
        int y = i.first, w = i.second;
        if(y == fa) continue;
        dfs(y, now);
        ans += w * abs(arr[y]);
        arr[now] += arr[y];
    }
}

int main(){
    scanf("%lld", &n);
    for(int i = 1; i <= n; i ++)
        scanf("%lld", &arr[i]);
    for(int i = 1; i < n; i ++){
        scanf("%lld%lld%lld", &u, &v, &c);
        e[u].push_back({v, c});
        e[v].push_back({u, c});
    }
    dfs(1, -1);
    printf("%lld\n", ans);
    return 0;
}