Let us regard the given tree rooted at vertex \(1\), and “particles” refer to positrons and electrons.

Let us consider the contribution of edge \(j\) to the answer. Without loss of generality, suppose that vertex \(u_j\) is the parent of vertex \(v_j\).

Let \(X_j\) be the sum of \(x\) over the vertices in the subtree rooted at vertex \(v_j\). No matter how you operate within this subtree, \(|X_j|\) particles with remain. To annihilate these particles, one has to move them via edge \(j\) to the outside of the subtree, or introduce particles from outside the subtree to pair with them. In any case, at least \(|X_j|\) particles need to be moved along edge \(j\), which contributes by at least \(|X_j| w_j\) to the answer. Thus, the answer is at least \(\sum_{j=1}^{N-1} |X_j| w_j\).

In fact, there exists a procedure that achieves this lower bound. Specifically, we inspect the vertices from the leaves, and if the vertex still contains particles, move it toward the parent.

Therefore, the optimal solution is \(\sum_{j=1}^{N-1} |X_j| w_j\). \(X_j\) can be found with Depth-First Search (DFS). The time complexity is \(O(N)\).

Sample code (Python)

N = int(input())
x = list(map(int, input().split()))
T = [[] for _ in range(N)]
for _ in range(N - 1):
    u, v, w = map(int, input().split())
    u -= 1
    v -= 1
    T[u].append((v, w))
    T[v].append((u, w))

ans = 0
st = [(0, -1, 0)]
while st:
    v, p, t = st.pop()
    if t == 0:
        st.append((v, p, 1))
        for u, w in T[v]:
            if u != p:
                st.append((u, v, 0))
    else:
        for u, w in T[v]:
            if u == p:
                continue
            ans += w * abs(x[u])
            x[v] += x[u]
print(ans)

Sample code (C++)

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N;
    cin >> N;
    vector<long long> x(N);
    for (auto& y : x) cin >> y;
    vector<vector<pair<int, long long>>> T(N);
    for (int i = 0; i < N - 1; ++i) {
        int u, v;
        long long w;
        cin >> u >> v >> w;
        --u, --v;
        T[u].push_back({v, w});
        T[v].push_back({u, w});
    }

    long long ans = 0;

    auto dfs = [&](auto& dfs, int v, int p) -> void {
        for (auto [c, w] : T[v]) {
            if (c == p) continue;
            dfs(dfs, c, v);
            ans += w * abs(x[c]);
            x[v] += x[c];
        }
    };

    dfs(dfs, 0, -1);
    cout << ans << endl;
}