#1177708 (C++17) No.3755 Root for Your Route

• 問題: No.3755 Root for Your Route
• ユーザー: marc2825
• 提出日時: 2026-08-19 23:46:58
• 言語: C++17 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: WA
• 実行時間: -
• コード長: 4,642 bytes
• コンパイル時間: 1,639 ms
• コンパイル使用メモリ: 243,024 KB
• 実行使用メモリ: 20,036 KB
• 最終ジャッジ日時: 2026-10-02 21:03:58
• 合計ジャッジ時間: 11,697 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge4_1

ファイルパターン	結果
sample	AC * 1
other	AC * 22 WA * 17

ソースコード

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

struct Line {
    mutable ll k, m, p;
    bool operator<(const Line& o) const { return k < o.k; }
    bool operator<(ll x) const { return p < x; }
};

struct CHT : multiset<Line, less<>> {
    static const ll INF = LLONG_MAX;

    ll div_floor(ll a, ll b) {
        return a / b - ((a ^ b) < 0 && a % b);
    }

    bool isect(iterator x, iterator y) {
        if (y == end()) {
            x->p = INF;
            return false;
        }
        if (x->k == y->k) {
            x->p = (x->m > y->m ? INF : -INF);
        } else {
            x->p = div_floor(y->m - x->m, x->k - y->k);
        }
        return x->p >= y->p;
    }

    void add(ll k, ll m) {
        auto z = insert({k, m, 0});
        auto y = z++;
        auto x = y;

        while (isect(y, z)) z = erase(z);
        if (x != begin() && isect(--x, y)) {
            isect(x, y = erase(y));
        }
        while ((y = x) != begin() && (--x)->p >= y->p) {
            isect(x, erase(y));
        }
    }

    ll query(ll x) {
        auto l = *lower_bound(x);
        return l.k * x + l.m;
    }
};

struct Node {
    int v, p, d;
    ll b;
};

int N;
vector<ll> A, ans, best, sub;
vector<vector<int>> G;
vector<int> sz, par;
vector<bool> used;

int get_centroid(int s) {
    vector<int> vs, st = {s};
    par[s] = -1;

    while (!st.empty()) {
        int v = st.back();
        st.pop_back();
        vs.push_back(v);

        for (int u : G[v]) {
            if (used[u] || u == par[v]) continue;
            par[u] = v;
            st.push_back(u);
        }
    }

    for (int i = (int)vs.size() - 1; i >= 0; --i) {
        int v = vs[i];
        sz[v] = 1;

        for (int u : G[v]) {
            if (!used[u] && par[u] == v) {
                sz[v] += sz[u];
            }
        }
    }

    int n = vs.size();

    for (int v : vs) {
        int mx = n - sz[v];

        for (int u : G[v]) {
            if (!used[u] && par[u] == v) {
                mx = max(mx, sz[u]);
            }
        }

        if (mx * 2 <= n) return v;
    }

    return -1;
}

void solve(int s) {
    int c = get_centroid(s);
    vector<vector<Node>> comps;

    for (int root : G[c]) {
        if (used[root]) continue;

        struct State {
            int v, p, d;
            ll sum;
        };

        vector<Node> cur;
        vector<State> st = {{root, c, 1, A[c] + A[root]}};

        while (!st.empty()) {
            auto [v, p, d, sum] = st.back();
            st.pop_back();

            ll b = sum - 1LL * d * (d + 1) / 2;
            cur.push_back({v, p, d, b});

            for (int u : G[v]) {
                if (used[u] || u == p) continue;
                st.push_back({u, v, d + 1, sum + A[u]});
            }
        }

        comps.push_back(move(cur));
    }

    {
        CHT cht;
        cht.add(0, A[c]);

        for (auto& cur : comps) {
            for (auto& [v, p, d, b] : cur) {
                best[v] = cht.query(d);
            }
            for (auto& [v, p, d, b] : cur) {
                cht.add(-d, b);
            }
        }
    }

    {
        CHT cht;
        cht.add(0, A[c]);

        for (int i = (int)comps.size() - 1; i >= 0; --i) {
            for (auto& [v, p, d, b] : comps[i]) {
                best[v] = max(best[v], cht.query(d));
            }
            for (auto& [v, p, d, b] : comps[i]) {
                cht.add(-d, b);
            }
        }
    }

    // s=t=c を考慮しない
    ll best_c = -(1LL << 60);

    for (auto& cur : comps) {
        for (auto& [v, p, d, b] : cur) {
            sub[v] = b - A[c] + best[v];
            best_c = max(best_c, sub[v]);
        }

        for (int i = (int)cur.size() - 1; i >= 0; --i) {
            auto [v, p, d, b] = cur[i];

            ans[v] = max(ans[v], sub[v]);

            if (p != c) {
                sub[p] = max(sub[p], sub[v]);
            }
        }
    }

    ans[c] = max(ans[c], best_c);

    used[c] = true;

    for (int u : G[c]) {
        if (!used[u]) {
            solve(u);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N;

    A.resize(N);
    for (ll& x : A) cin >> x;

    G.resize(N);

    for (int i = 0; i < N - 1; ++i) {
        int u, v;
        cin >> u >> v;
        --u, --v;

        G[u].push_back(v);
        G[v].push_back(u);
    }

    sz.resize(N);
    par.resize(N);
    used.assign(N, false);

    // s=t=r を初期値として入れない
    ans.assign(N, -(1LL << 60));

    best.resize(N);
    sub.resize(N);

    solve(0);

    cout << *min_element(ans.begin(), ans.end()) << '\n';
}