【AtCoder】ABC 409 E - Pair Annihilation | 緑コーダーが解くAtCoder

配点: 425 点 / 実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 973 / NoviSteps: 1Q

E問題「木上のクーロン」←やかましくて草
— あじゃじゃ (@asian202388) 2025年6月7日

問題概要
制約
考察
実装例
コメント

問題概要

$N$ 頂点の木が与えられ、辺 $j$ は頂点 $u_j,v_j$ を双方向に結び、重み $w_j$ を持つ。また、頂点 $i$ には整数 $x_i$ が与えられており、 $x_i \gt 0$ なら $x_i$ 個の陽電子が、 $x_i \lt 0$ なら $-x_i$ 個の電子が頂点 $i$ に置かれていて、 $x_i=0$ ならば頂点 $i$ には何もない。ここで、 $\displaystyle \sum_{i=1}^N x_i = 0$ が保証される。

陽電子または電子1個を辺 $j$ に沿って動かすと、エネルギー $w_j$ がかかる。また、陽電子と電子が同じ頂点にあるとき、それらは同じ数だけ打ち消し合って消滅する。

すべての陽電子と電子を消滅させるために必要なエネルギーの最小値を求めよ。

制約

$2 \leq N \leq 10^5$
$|x_i| \leq 10^4$
$0 \leq w_j \leq 10^4$
入力はすべて整数

考察

本問のような、グラフ上で辺に沿ってモノを動かすような操作をする場合は、「辺に注目して考える」というのが有効なことが多い。

今回も下図のように、木上の赤い辺に注目して、この辺を通過する荷電粒子(陽電子と電子)の数を最小化することを考える。

この場合、「赤い辺の左右一方に接続されている部分木内の荷電粒子をできるだけ対消滅させて、赤い辺を通して反対側へ送る」というようなことを行えばよい。送る前にできるだけ数を少なくするのが重要(当たり前ではあるが)

この操作に必要なエネルギーの下界は、部分木内の電荷の総和を $C$ 、赤い辺の重みを $w$ とすれば、 $|C| w$ と書くことができる。これより少ないエネルギーで荷電粒子を部分木の外部に送ることはできない。

あとは、この下界を木上の全ての辺において達成するような方法を考える。

それは、ある1つの頂点を根としたときに、「可能な限り対消滅をさせながら、葉からボトムアップで荷電粒子を根の方に移動させていく」というものだ。

これは、 DFS で帰りがけ順に再帰的に探索することで実現できる。詳しくは実装例を参照。

実装例

#include <bits/stdc++.h>

#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)

using namespace std;

using ll = long long;
template <class T>
using Graph = vector<vector<T>>;

// ======================================== //

struct Edge
{
    int to;
    ll cost;
};

int main()
{
    int N;
    cin >> N;
    vector<int> X(N);
    rep(i, 0, N) cin >> X[i];

    Graph<Edge> G(N);
    rep(i, 0, N - 1)
    {
        int u, v;
        ll w;
        cin >> u >> v >> w;
        u--, v--;
        G[u].push_back({v, w});
        G[v].push_back({u, w});
    }

    ll ans = 0;

    auto dfs = [&](auto self, int now, int parent) -> ll
    {
        ll charge_sum = X[now];

        for (auto &&e : G[now])
        {
            if (e.to == parent)
                continue;

            ll charge_sum_child = self(self, e.to, now);
            ans += abs(charge_sum_child) * e.cost;
            charge_sum += charge_sum_child;
        }

        return charge_sum;
    };

    dfs(dfs, 0, -1);

    cout << ans << endl;

    return 0;
}