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

• 問題: No.3755 Root for Your Route
• ユーザー: marc2825
• 提出日時: 2026-09-17 14:08:05
• 言語: C++17 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 170 ms / 3,000 ms
• コード長: 9,155 bytes
• コンパイル時間: 1,490 ms
• コンパイル使用メモリ: 235,736 KB
• 実行使用メモリ: 13,568 KB
• 最終ジャッジ日時: 2026-10-02 21:06:57
• 合計ジャッジ時間: 9,179 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge2_1

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

ソースコード

// GNU++17
// 時間計算量: O(N log N)
// 空間計算量: O(N)
//
// 重心を両方の子問題に残す二分分解。
// 各分割を BFS 順 + 静的な単調 CHT で線形時間処理する。

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

using i64 = long long;
using i128 = __int128_t;

struct Edge {
    int u;
    int v;
};

// 傾き非減少順に全直線を追加した後、
// x 非減少順に最大値クエリを行う。
struct MonotoneMaxCHT {
    struct Line {
        i64 m;
        i64 b;

        i64 eval(i64 x) const {
            return m * x + b;
        }
    };

    vector<Line> lines;
    size_t ptr = 0;

    void reserve(size_t capacity) {
        lines.reserve(capacity);
    }

    static bool redundant(
        const Line& a,
        const Line& b,
        const Line& c
    ) {
        // intersection(a, b) >= intersection(b, c)
        // 交差積は 64 bit を超え得るので 128 bit で比較する。
        return static_cast<i128>(a.b - b.b) * (c.m - b.m)
            >= static_cast<i128>(b.b - c.b) * (b.m - a.m);
    }

    void add(i64 m, i64 b) {
        Line line{m, b};

        if (!lines.empty() && lines.back().m == m) {
            if (lines.back().b >= b) {
                return;
            }
            lines.pop_back();
        }

        while (lines.size() >= 2) {
            size_t n = lines.size();

            if (!redundant(lines[n - 2], lines[n - 1], line)) {
                break;
            }

            lines.pop_back();
        }

        lines.push_back(line);
    }

    i64 query(i64 x) {
        while (
            ptr + 1 < lines.size()
            && lines[ptr].eval(x) <= lines[ptr + 1].eval(x)
        ) {
            ++ptr;
        }

        return lines[ptr].eval(x);
    }
};

vector<i64> A;
vector<i64> F;

// 元頂点番号から、その子問題における局所頂点番号への対応。
// 子問題ごとに N 要素を初期化せず、使用した場所だけ戻す。
vector<int> local_id;

// この子問題で左右をまたぐパスを処理し、
// 辺集合を二分して返す。共有する重心は両方に残る。
array<vector<Edge>, 2> process(const vector<Edge>& edges) {
    const int m = static_cast<int>(edges.size());
    const int n = m + 1;

    // この子問題の辺だけから局所的な隣接リストを構築する。
    // 元の隣接リスト全体を毎回走査しないことが重要。
    vector<int> original;
    original.reserve(n);

    vector<int> head(n, -1);
    vector<int> to(2 * m);
    vector<int> nxt(2 * m);
    int arc_count = 0;

    auto get_id = [&](int v) -> int {
        if (local_id[v] == -1) {
            local_id[v] = static_cast<int>(original.size());
            original.push_back(v);
        }
        return local_id[v];
    };

    auto add_arc = [&](int u, int v) {
        to[arc_count] = v;
        nxt[arc_count] = head[u];
        head[u] = arc_count;
        ++arc_count;
    };

    for (const Edge& e : edges) {
        int u = get_id(e.u);
        int v = get_id(e.v);

        add_arc(u, v);
        add_arc(v, u);
    }

    for (int v : original) {
        local_id[v] = -1;
    }

    // 仮に頂点 0 を根として BFS する。
    vector<int> parent(n, -1);
    vector<int> order;
    order.reserve(n);
    order.push_back(0);

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

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

            if (u == parent[v]) {
                continue;
            }

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

    // 通常の頂点重心を求める。
    vector<int> subtree_size(n, 1);
    int c = -1;

    for (int i = n - 1; i >= 0; --i) {
        int v = order[i];
        int largest = 0;

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

            if (u == parent[v]) {
                continue;
            }

            subtree_size[v] += subtree_size[u];
            largest = max(largest, subtree_size[u]);
        }

        largest = max(largest, n - subtree_size[v]);

        if (largest <= n / 2) {
            c = v;
        }
    }

    // 重心 c を根として BFS し直す。
    //
    // branch[v]: v が属する、c を除いた連結成分の番号
    // depth[v] : c からの辺数
    // B[v]     : c-v パスの頂点値の和 - T(depth[v])
    vector<int> depth(n, 0);
    vector<int> branch(n, -1);
    vector<int> branch_size;
    branch_size.reserve(n);

    vector<i64> B(n);
    const i64 ac = A[original[c]];

    order.clear();
    order.push_back(c);
    parent[c] = -1;
    B[c] = ac;

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

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

            if (u == parent[v]) {
                continue;
            }

            parent[u] = v;
            depth[u] = depth[v] + 1;

            // T(d) - T(d - 1) = d
            B[u] = B[v] + A[original[u]] - depth[u];

            if (v == c) {
                branch[u] = static_cast<int>(branch_size.size());
                branch_size.push_back(0);
            } else {
                branch[u] = branch[v];
            }

            ++branch_size[branch[u]];
            order.push_back(u);
        }
    }

    // 枝を二分し、両側の辺数を [m/3, 2m/3] にする。
    // 枝の頂点数は、c との接続辺を含めた枝の辺数に等しい。
    const int k = static_cast<int>(branch_size.size());
    vector<int> branch_side(k, 1);

    int left_edges = 0;

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

    if (left_edges == 0) {
        for (int i = 0; i < k; ++i) {
            branch_side[i] = 0;
            left_edges += branch_size[i];

            if (3 * left_edges >= m) {
                break;
            }
        }
    }

    // c を通る u-v パスの得点:
    // B[u] + B[v] - A[c] - depth[u] * depth[v]
    //
    // 各側について直線 -depth[v] * x + B[v] を登録する。
    MonotoneMaxCHT hulls[2];
    hulls[0].reserve(left_edges + 1);
    hulls[1].reserve(m - left_edges + 1);

    // 逆 BFS 順なら距離は非増加、傾きは非減少。
    for (int i = n - 1; i >= 1; --i) {
        int v = order[i];
        int side = branch_side[branch[v]];

        hulls[side].add(-static_cast<i64>(depth[v]), B[v]);
    }

    // c を端点にするパスも許す。
    // 傾き 0 は最大なので、最後に追加する。
    hulls[0].add(0, ac);
    hulls[1].add(0, ac);

    vector<i64> best(n, -(1LL << 60));
    best[c] = ac;

    // BFS 順ならクエリ位置 depth[v] は非減少。
    // 両側の全頂点について、反対側の hull に問い合わせる。
    for (int i = 1; i < n; ++i) {
        int v = order[i];
        int side = branch_side[branch[v]];

        best[v] = B[v] - ac
            + hulls[side ^ 1].query(depth[v]);
    }

    // best[v] を部分木最大値にして、元頂点の答えへ反映する。
    //
    // 伝播するのは今回の重心を通るパスの値だけ。
    // グローバルな F の値を親へ伝播してはいけない。
    for (int i = n - 1; i >= 0; --i) {
        int v = order[i];

        F[original[v]] = max(F[original[v]], best[v]);

        if (parent[v] != -1) {
            best[parent[v]] = max(best[parent[v]], best[v]);
        }
    }

    // 子問題を元の頂点番号による辺リストで作る。
    // 辺は重複せず、重心 c だけが両方の子問題に現れる。
    array<vector<Edge>, 2> children;
    children[0].reserve(left_edges);
    children[1].reserve(m - left_edges);

    for (int i = 1; i < n; ++i) {
        int v = order[i];
        int side = branch_side[branch[v]];

        children[side].push_back({
            original[parent[v]],
            original[v]
        });
    }

    return children;
}

void decompose(vector<Edge> edges) {
    if (edges.empty()) {
        return;
    }

    if (edges.size() == 1) {
        int u = edges[0].u;
        int v = edges[0].v;

        i64 score = A[u] + A[v] - 1;
        F[u] = max(F[u], score);
        F[v] = max(F[v], score);
        return;
    }

    auto children = process(edges);

    // 再帰前に親の辺リストを解放する。
    // process() 内の作業領域も、この時点で解放済み。
    vector<Edge>().swap(edges);

    decompose(move(children[0]));
    decompose(move(children[1]));
}

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

    int N;
    cin >> N;

    A.resize(N);

    for (i64& x : A) {
        cin >> x;
    }

    // 単一頂点のパスを最初から考慮する。
    F = A;
    local_id.assign(N, -1);

    vector<Edge> edges(N - 1);

    for (Edge& e : edges) {
        cin >> e.u >> e.v;
        --e.u;
        --e.v;
    }

    decompose(move(edges));

    cout << *min_element(F.begin(), F.end()) << '\n';
    return 0;
}