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

• 問題: No.3755 Root for Your Route
• ユーザー: marc2825
• 提出日時: 2026-08-20 00:10:27
• 言語: C++17 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 243 ms / 3,000 ms
• コード長: 6,443 bytes
• コンパイル時間: 1,402 ms
• コンパイル使用メモリ: 229,072 KB
• 実行使用メモリ: 19,644 KB
• 最終ジャッジ日時: 2026-10-02 21:03:50
• 合計ジャッジ時間: 10,663 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge4_0

ファイルパターン	結果
sample	AC * 1
other	AC * 39

ソースコード

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

using ll = long long;
using i128 = __int128_t;

struct Line {
    ll k, b;
};

int N;
vector<ll> A, ans, pref, B, qv, sub;
vector<int> U, V;
vector<int> par, sz, dep, branch, color;

// 現在の部分木だけからなる一時的な隣接リスト
vector<int> head, to_, nxt_;

ll value(const Line& l, ll x) {
    return l.k * x + l.b;
}

// b が不要か
bool bad(const Line& a, const Line& b, const Line& c) {
    return (i128)(a.b - b.b) * (c.k - b.k)
         >= (i128)(b.b - c.b) * (b.k - a.k);
}

// src の頂点を直線として、dst の各頂点を処理
void apply_cht(const vector<int>& src, const vector<int>& dst) {
    vector<Line> hull;

    // src は距離昇順なので、逆順なら傾き -d は昇順
    for (int i = (int)src.size() - 1; i >= 0; --i) {
        int v = src[i];
        Line l{-dep[v], B[v]};

        if (!hull.empty() && hull.back().k == l.k) {
            if (hull.back().b >= l.b) continue;
            hull.pop_back();
        }

        while (hull.size() >= 2 &&
               bad(hull[hull.size() - 2], hull.back(), l)) {
            hull.pop_back();
        }

        hull.push_back(l);
    }

    // dst も距離昇順なので query も単調
    int p = 0;

    for (int v : dst) {
        ll x = dep[v];

        while (p + 1 < (int)hull.size() &&
               value(hull[p], x) <= value(hull[p + 1], x)) {
            ++p;
        }

        qv[v] = B[v] + value(hull[p], x);
    }
}

// 辺集合 es から一時的な木を作る
void build_graph(const vector<int>& es) {
    for (int e : es) {
        head[U[e]] = -1;
        head[V[e]] = -1;
    }

    to_.resize(2 * es.size());
    nxt_.resize(2 * es.size());

    int p = 0;

    for (int e : es) {
        int u = U[e], v = V[e];

        to_[p] = v;
        nxt_[p] = head[u];
        head[u] = p++;

        to_[p] = u;
        nxt_[p] = head[v];
        head[v] = p++;
    }
}

// 現在の木の重心
int get_centroid(const vector<int>& es) {
    int s = U[es[0]];

    vector<int> order = {s};
    par[s] = -1;

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

        for (int e = head[v]; e != -1; e = nxt_[e]) {
            int u = to_[e];
            if (u == par[v]) continue;

            par[u] = v;
            order.push_back(u);
        }
    }

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

        for (int e = head[v]; e != -1; e = nxt_[e]) {
            int u = to_[e];
            if (par[u] == v) sz[v] += sz[u];
        }
    }

    int n = order.size();

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

        for (int e = head[v]; e != -1; e = nxt_[e]) {
            int u = to_[e];
            if (par[u] == v) mx = max(mx, sz[u]);
        }

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

    return -1;
}

void solve(vector<int> es) {
    int m = es.size();

    // 1辺なら、そのパスをそのまま処理
    if (m == 1) {
        int e = es[0];
        int u = U[e], v = V[e];

        ll val = A[u] + A[v] - 1;

        ans[u] = max(ans[u], val);
        ans[v] = max(ans[v], val);

        return;
    }

    build_graph(es);

    int c = get_centroid(es);

    // c を根として BFS
    vector<int> order = {c};

    par[c] = -1;
    dep[c] = 0;
    pref[c] = A[c];

    vector<int> bsz;

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

        for (int e = head[v]; e != -1; e = nxt_[e]) {
            int u = to_[e];

            if (u == par[v]) continue;

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

            if (v == c) {
                branch[u] = bsz.size();
                bsz.push_back(0);
            } else {
                branch[u] = branch[v];
            }

            ++bsz[branch[u]];

            B[u] = pref[u]
                 - 1LL * dep[u] * (dep[u] + 1) / 2;

            order.push_back(u);
        }
    }

    // 枝を [1/3, 2/3] に分割
    int k = bsz.size();
    int red_size = 0;
    int pick = -1;

    vector<int> bcolor(k, 1);

    for (int i = 0; i < k; ++i) {
        if (3 * bsz[i] >= m) {
            pick = i;
            break;
        }
    }

    if (pick != -1) {
        bcolor[pick] = 0;
        red_size = bsz[pick];
    } else {
        for (int i = 0; i < k && 3 * red_size < m; ++i) {
            bcolor[i] = 0;
            red_size += bsz[i];
        }
    }

    vector<int> red, blue;

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

        color[v] = bcolor[branch[v]];

        if (color[v] == 0) red.push_back(v);
        else blue.push_back(v);
    }

    // 赤-青間の最適パス
    apply_cht(blue, red);
    apply_cht(red, blue);

    ll best_c = ans[c];

    for (int v : red) {
        qv[v] -= A[c];
        sub[v] = qv[v];
        best_c = max(best_c, qv[v]);
    }

    for (int v : blue) {
        qv[v] -= A[c];
        sub[v] = qv[v];
        best_c = max(best_c, qv[v]);
    }

    // 各端点の値を c 方向へ伝播
    for (int i = (int)order.size() - 1; i >= 1; --i) {
        int v = order[i];

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

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

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

    // 赤側・青側の辺集合へ再帰
    vector<int> e0, e1;

    for (int e : es) {
        int u = U[e], v = V[e];

        int side;

        if (u == c) side = color[v];
        else if (v == c) side = color[u];
        else side = color[u];

        if (side == 0) e0.push_back(e);
        else e1.push_back(e);
    }

    solve(move(e0));
    solve(move(e1));
}

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

    cin >> N;

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

    U.resize(N - 1);
    V.resize(N - 1);

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

        U[e] = u;
        V[e] = v;
    }

    // s = t = r
    ans = A;

    pref.resize(N);
    B.resize(N);
    qv.resize(N);
    sub.resize(N);

    par.resize(N);
    sz.resize(N);
    dep.resize(N);
    branch.resize(N);
    color.resize(N);
    head.assign(N, -1);

    vector<int> edges(N - 1);
    iota(edges.begin(), edges.end(), 0);

    solve(move(edges));

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