题解：AT_abc409_e [ABC409E] Pair Annihilation

wuxikai · 2025-12-11 13:59:35 · 题解

拓扑。

考虑有 u 到 v 的边，边权为 w，且 u 只有 v 这一个还没被拓扑遍历过，那么 u 显然只能把粒子全部传递过去，和 v 中的粒子尽量湮灭，记录传递的粒子数量 \times w 的花费即可。

#include<bits/stdc++.h>
#define int long long // 十年OI一场空，不开______见祖宗 
using namespace std;
const int N = 1e5+7;
struct edge{
    int v,w;
};
int n,ans;
bool vis[N];
int cnt[N],du[N];
vector<edge> g[N];
void topo(){
    queue<int> q;
    for(int i=1;i<=n;i++){
        if(du[i]==1) q.push(i);
    }
    q.pop(); // 核心出装：默认某个节点为根，将无根树变化成有根树 
    while(!q.empty()){
        int u=q.front();
        q.pop();
        vis[u]=true;// 标记来过
        for(edge e:g[u]){
            int v=e.v,w=e.w;
            if(vis[v]) continue;// 来过的直接跳 
            cnt[v]+=cnt[u];
            ans+=abs(cnt[u])*w;
            du[v]--;
            if(du[v]==1){
                q.push(v);
                vis[v]=true;// 防止多次入队 
            }
        }
    }
}
signed main(){
    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> cnt[i];
    }
    for(int i=1;i<n;i++){
        int u,v,w;
        cin >> u >> v >> w;
        g[u].push_back({v,w});
        g[v].push_back({u,w});
        du[u]++;
        du[v]++;
    }
    topo();
    cout << ans;
    return 0;
}