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

• 問題: No.3755 Root for Your Route
• ユーザー: marc2825
• 提出日時: 2026-10-02 17:32:40
• 言語: C++17 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 135 ms / 3,000 ms
• コード長: 6,182 bytes
• コンパイル時間: 1,413 ms
• コンパイル使用メモリ: 233,716 KB
• 実行使用メモリ: 16,744 KB
• 最終ジャッジ日時: 2026-10-02 21:07:17
• 合計ジャッジ時間: 7,263 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge1_0

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

ソースコード

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

using ll = long long;

struct LiChaoTree {
    static constexpr ll NEG = -(1LL << 62);

    struct Line {
        ll m;
        ll b;

        ll value(int x) const {
            return m * x + b;
        }
    };

    int xmax;
    vector<Line> tree;

    explicit LiChaoTree(int xmax)
        : xmax(xmax),
          tree(4 * (xmax + 1), Line{0, NEG}) {
    }

    void add_line(Line line, int node, int left, int right) {
        if (tree[node].b == NEG) {
            tree[node] = line;
            return;
        }

        int mid = (left + right) / 2;

        if (line.value(mid) > tree[node].value(mid)) {
            swap(line, tree[node]);
        }

        if (left == right) {
            return;
        }

        if (line.value(left) > tree[node].value(left)) {
            add_line(line, node * 2, left, mid);
        } else if (line.value(right) > tree[node].value(right)) {
            add_line(line, node * 2 + 1, mid + 1, right);
        }
    }

    void add_line(ll m, ll b) {
        add_line(Line{m, b}, 1, 0, xmax);
    }

    ll query(int x) const {
        int node = 1;
        int left = 0;
        int right = xmax;
        ll result = NEG;

        while (true) {
            if (tree[node].b == NEG) {
                break;
            }

            result = max(result, tree[node].value(x));

            if (left == right) {
                break;
            }

            int mid = (left + right) / 2;

            if (x <= mid) {
                node *= 2;
                right = mid;
            } else {
                node = node * 2 + 1;
                left = mid + 1;
            }
        }

        return result;
    }
};

vector<vector<int>> graph;
vector<ll> A, answer, B, best;
vector<int> parent, subtree_size, depth;
vector<char> removed;

pair<int, int> find_centroid(int start) {
    vector<int> order;
    order.push_back(start);
    parent[start] = -1;

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

        for (int u : graph[v]) {
            if (removed[u] || u == parent[v]) {
                continue;
            }

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

    int total = (int)order.size();

    for (int i = total - 1; i > 0; --i) {
        int v = order[i];
        subtree_size[parent[v]] += subtree_size[v];
    }

    int centroid = start;

    for (int v : order) {
        int largest = total - subtree_size[v];

        for (int u : graph[v]) {
            if (removed[u] || u == parent[v]) {
                continue;
            }

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

        if (largest <= total / 2) {
            centroid = v;
            break;
        }
    }

    return {centroid, total};
}

void process_centroid(int c, int component_size) {
    vector<int> order;
    vector<pair<int, int>> groups;

    order.reserve(component_size);
    order.push_back(c);

    parent[c] = -1;
    depth[c] = 0;
    B[c] = A[c];
    best[c] = A[c];

    int max_depth = 0;

    // 各成分を連続した区間として列挙する。
    // 各区間内では、親が子より先に並ぶ。
    for (int root : graph[c]) {
        if (removed[root]) {
            continue;
        }

        int left = (int)order.size();

        parent[root] = c;
        depth[root] = 1;
        B[root] = A[c] + A[root] - 1;
        best[root] = B[root];
        order.push_back(root);

        for (int i = left; i < (int)order.size(); ++i) {
            int v = order[i];
            max_depth = max(max_depth, depth[v]);

            for (int u : graph[v]) {
                if (removed[u] || u == parent[v]) {
                    continue;
                }

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

                // 新しい辺の移動時間は depth[u]。
                B[u] = B[v] + A[u] - depth[u];
                best[u] = B[u];

                order.push_back(u);
            }
        }

        groups.emplace_back(left, (int)order.size());
    }

    // 順方向と逆方向の二度処理する。
    for (int pass = 0; pass < 2; ++pass) {
        LiChaoTree hull(max_depth);
        hull.add_line(0, A[c]);

        for (auto [left, right] : groups) {
            // 同じ成分の直線を追加する前に、全クエリを行う。
            for (int i = left; i < right; ++i) {
                int v = order[i];

                ll candidate =
                    B[v] - A[c] + hull.query(depth[v]);

                best[v] = max(best[v], candidate);
            }

            for (int i = left; i < right; ++i) {
                int v = order[i];
                hull.add_line(-depth[v], B[v]);
            }
        }

        reverse(groups.begin(), groups.end());
    }

    // 端点の最大得点を、その端点から重心までの全頂点へ伝播する。
    for (int i = (int)order.size() - 1; i > 0; --i) {
        int v = order[i];

        answer[v] = max(answer[v], best[v]);
        best[parent[v]] = max(best[parent[v]], best[v]);
    }

    answer[c] = max(answer[c], best[c]);
}

void decompose(int start) {
    auto [c, component_size] = find_centroid(start);

    removed[c] = true;

    if (component_size == 1) {
        return;
    }

    process_centroid(c, component_size);

    for (int u : graph[c]) {
        if (!removed[u]) {
            decompose(u);
        }
    }
}

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

    int N;
    cin >> N;

    A.resize(N);

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

    graph.resize(N);

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

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

    // 単一頂点のパスを最初から考慮する。
    answer = A;

    B.resize(N);
    best.resize(N);
    parent.resize(N);
    subtree_size.resize(N);
    depth.resize(N);
    removed.assign(N, false);

    decompose(0);

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

    return 0;
}