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

• 問題: No.3755 Root for Your Route
• ユーザー: marc2825
• 提出日時: 2026-08-20 00:55:06
• 言語: C++17 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: WA
• 実行時間: -
• コード長: 5,400 bytes
• コンパイル時間: 1,338 ms
• コンパイル使用メモリ: 230,428 KB
• 実行使用メモリ: 13,928 KB
• 最終ジャッジ日時: 2026-10-02 21:04:42
• 合計ジャッジ時間: 9,330 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge4_0

ファイルパターン	結果
sample	AC * 1
other	AC * 8 WA * 4 TLE * 1 -- * 26

ソースコード

#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;
    }
};


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

    int N;
    cin >> N;

    vector<ll> A(N);
    for (auto& x : A) cin >> x;

    vector<vector<int>> G(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);
    }

    bool is_path = true;

    for (int v = 0; v < N; ++v) {
        if ((int)G[v].size() > 2) {
            is_path = false;
        }
    }

    // パスなら専用高速処理
    if (is_path) {
        int s = 0;

        while ((int)G[s].size() != 1) ++s;

        vector<int> P;
        int p = -1, v = s;

        while (true) {
            P.push_back(v);

            int nxt = -1;

            for (int u : G[v]) {
                if (u != p) {
                    nxt = u;
                    break;
                }
            }

            if (nxt == -1) break;

            p = v;
            v = nxt;
        }

        vector<ll> pref(N + 1);

        for (int i = 0; i < N; ++i) {
            pref[i + 1] = pref[i] + A[P[i]];
        }

        vector<ll> L(N), R(N);

        // 左端 s <= r、右端 t >= r を含むパス
        //
        // score(s,t)
        // = pref[t+1]-pref[s] - T(t-s)
        //
        // T(t-s)
        // を展開して CHT で処理する。

        {
            CHT cht;

            for (int r = 0; r < N; ++r) {
                // s を直線として追加
                //
                // score(s,r)
                // = pref[r+1] - pref[s]
                //   - (r-s)(r-s+1)/2
                //
                // 2倍して整理する
                ll k = 2LL * r;
                ll b = -2LL * pref[r]
                     - 1LL * r * r
                     + r;

                cht.add(k, b);

                ll x = r;

                L[r] =
                    (2LL * pref[r + 1]
                     - 1LL * r * r
                     - r
                     + cht.query(x)) / 2;
            }
        }

        {
            vector<ll> B = A;
            reverse(B.begin(), B.end());

            vector<ll> q(N + 1);

            for (int i = 0; i < N; ++i) {
                q[i + 1] = q[i] + B[i];
            }

            CHT cht;

            for (int i = 0; i < N; ++i) {
                ll k = 2LL * i;
                ll b = -2LL * q[i]
                     - 1LL * i * i
                     + i;

                cht.add(k, b);

                ll val =
                    (2LL * q[i + 1]
                     - 1LL * i * i
                     - i
                     + cht.query(i)) / 2;

                R[N - 1 - i] = val;
            }
        }

        // これは片側だけの候補しか見ていないので、
        // 一般にはここもさらに処理が必要。
        // 嘘解法として簡単な近似を使う。
        ll answer = (1LL << 62);

        for (int i = 0; i < N; ++i) {
            answer = min(answer, max({A[P[i]], L[i], R[i]}));
        }

        cout << answer << '\n';
        return 0;
    }


    // 一般木では自然な O(N^2) DP
    const ll NEG = -(1LL << 60);

    vector<ll> ans(N, NEG);

    vector<int> par(N), dep(N), order;
    vector<ll> sum(N), best(N);

    for (int s = 0; s < N; ++s) {
        order.clear();
        order.push_back(s);

        par[s] = -1;
        dep[s] = 0;
        sum[s] = A[s];

        for (int i = 0; i < (int)order.size(); ++i) {
            int v = order[i];

            for (int u : G[v]) {
                if (u == par[v]) continue;

                par[u] = v;
                dep[u] = dep[v] + 1;
                sum[u] = sum[v] + A[u];

                order.push_back(u);
            }
        }

        for (int v : order) {
            ll d = dep[v];
            best[v] = sum[v] - d * (d + 1) / 2;
        }

        for (int i = N - 1; i > 0; --i) {
            int v = order[i];
            int p = par[v];

            if (best[v] > best[p]) {
                best[p] = best[v];
            }
        }

        for (int v = 0; v < N; ++v) {
            if (best[v] > ans[v]) {
                ans[v] = best[v];
            }
        }
    }

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