Submission #52095713

---

Source Code Expand

/**
 *  @the_hyp0cr1t3
 *  06.04.2024 18:09
**/
#include <bits/stdc++.h>

using i64 = long long;

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);

    int n;
    std::cin >> n;
    std::vector<std::vector<int>> g(n);
    for (int i = 1; i < n; i++) {
        int u, v;
        std::cin >> u >> v;
        --u, --v;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }
    std::vector<int> c(n);
    for (auto &x : c)
        std::cin >> x;

    i64 C = std::accumulate(c.begin(), c.end(), 0LL);

    i64 sum = 0;
    std::vector<i64> sub(n);
    auto dfs = [&](auto &&self, int u, int p, int d) -> void {
        sum += 1LL * c[u] * d;
        sub[u] = c[u];
        for (auto v : g[u]) {
            if (v == p) continue;
            self(self, v, u, d + 1);
            sub[u] += sub[v];
        }
    };
    dfs(dfs, 0, -1, 0);

    i64 ans = LLONG_MAX;
    auto dfs2 = [&](auto &&self, int u, int p) -> void {
        ans = std::min(ans, sum);
        for (auto v : g[u]) {
            if (v == p) continue;
            sum += C - 2 * sub[v];
            self(self, v, u);
            sum -= C - 2 * sub[v];
        }
    };
    dfs2(dfs2, 0, -1);

    std::cout << ans << '\n';
}

Submission Info

Judge Result