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

• 問題: No.3755 Root for Your Route
• ユーザー: marc2825
• 提出日時: 2026-08-19 23:19:30
• 言語: C++17 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 330 ms / 3,000 ms
• コード長: 6,269 bytes
• コンパイル時間: 1,922 ms
• コンパイル使用メモリ: 251,800 KB
• 実行使用メモリ: 20,052 KB
• 最終ジャッジ日時: 2026-10-02 20:59:43
• 合計ジャッジ時間: 12,266 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge4_0

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

ソースコード

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

using ll = long long;

const ll NEG = -(1LL << 62);

struct Line {
    ll a = 0, b = NEG;
    bool exist = false;

    ll get(ll x) const {
        return a * x + b;
    }
};

struct LiChaoTree {
    int L, R;
    vector<Line> seg;

    LiChaoTree(int r = 0) {
        L = 0;
        R = max(0, r);
        seg.resize(4 * (R + 1) + 10);
    }

    void add_line(Line line) {
        add_line(line, 1, L, R);
    }

    void add_line(Line line, int k, int l, int r) {
        if (!seg[k].exist) {
            seg[k] = line;
            seg[k].exist = true;
            return;
        }

        int m = (l + r) / 2;

        bool left = line.get(l) > seg[k].get(l);
        bool mid = line.get(m) > seg[k].get(m);

        if (mid) {
            swap(line, seg[k]);
        }

        if (l == r) return;

        if (left != mid) {
            add_line(line, k * 2, l, m);
        } else {
            add_line(line, k * 2 + 1, m + 1, r);
        }
    }

    ll query(int x) const {
        return query(x, 1, L, R);
    }

    ll query(int x, int k, int l, int r) const {
        ll res = seg[k].exist ? seg[k].get(x) : NEG;

        if (l == r) return res;

        int m = (l + r) / 2;

        if (x <= m) {
            return max(res, query(x, k * 2, l, m));
        } else {
            return max(res, query(x, k * 2 + 1, m + 1, r));
        }
    }
};

struct Entry {
    int v;
    int parent;
    int dist;
    ll B;
};

int N;
vector<ll> A;
vector<vector<int>> G;

vector<int> sz;
vector<int> par;
vector<bool> dead;

vector<ll> ans;
vector<ll> partner;
vector<ll> submax_value;

int find_centroid(int start) {
    vector<int> nodes;
    vector<int> st = {start};

    par[start] = -1;

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

        nodes.push_back(v);

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

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

        sz[v] = 1;

        for (int to : G[v]) {
            if (dead[to]) continue;
            if (par[to] == v) {
                sz[v] += sz[to];
            }
        }
    }

    int M = nodes.size();

    for (int v : nodes) {
        int mx = M - sz[v];

        for (int to : G[v]) {
            if (dead[to]) continue;

            if (par[to] == v) {
                mx = max(mx, sz[to]);
            }
        }

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

    return -1;
}

void solve_centroid(int start) {
    int c = find_centroid(start);

    vector<vector<Entry>> comps;

    int max_dist = 0;

    for (int first : G[c]) {
        if (dead[first]) continue;

        vector<Entry> comp;

        struct State {
            int v;
            int parent;
            int dist;
            ll sum;
        };

        vector<State> st;

        st.push_back({
            first,
            c,
            1,
            A[c] + A[first]
        });

        while (!st.empty()) {
            State cur = st.back();
            st.pop_back();

            ll d = cur.dist;
            ll triangle = d * (d + 1) / 2;

            ll B = cur.sum - triangle;

            comp.push_back({
                cur.v,
                cur.parent,
                cur.dist,
                B
            });

            max_dist = max(max_dist, cur.dist);

            for (int to : G[cur.v]) {
                if (dead[to] || to == cur.parent) continue;

                st.push_back({
                    to,
                    cur.v,
                    cur.dist + 1,
                    cur.sum + A[to]
                });
            }
        }

        comps.push_back(move(comp));
    }

    {
        LiChaoTree cht(max_dist);

        cht.add_line({
            0,
            A[c],
            true
        });

        for (auto &comp : comps) {
            for (auto &e : comp) {
                partner[e.v] = cht.query(e.dist);
            }

            for (auto &e : comp) {
                cht.add_line({
                    -e.dist,
                    e.B,
                    true
                });
            }
        }
    }

    {
        LiChaoTree cht(max_dist);

        cht.add_line({
            0,
            A[c],
            true
        });

        for (int i = (int)comps.size() - 1; i >= 0; i--) {
            for (auto &e : comps[i]) {
                partner[e.v] =
                    max(partner[e.v], cht.query(e.dist));
            }

            for (auto &e : comps[i]) {
                cht.add_line({
                    -e.dist,
                    e.B,
                    true
                });
            }
        }
    }

    ll best_for_centroid = A[c];

    for (auto &comp : comps) {
        for (auto &e : comp) {
            ll q =
                e.B
                + partner[e.v]
                - A[c];

            submax_value[e.v] = q;

            best_for_centroid =
                max(best_for_centroid, q);
        }

        for (int i = (int)comp.size() - 1; i >= 0; i--) {
            auto &e = comp[i];

            ans[e.v] =
                max(ans[e.v], submax_value[e.v]);

            if (e.parent != c) {
                submax_value[e.parent] =
                    max(
                        submax_value[e.parent],
                        submax_value[e.v]
                    );
            }
        }
    }

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

    dead[c] = true;

    comps.clear();

    for (int to : G[c]) {
        if (!dead[to]) {
            solve_centroid(to);
        }
    }
}

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);
    dead.assign(N, false);

    ans = A;

    partner.assign(N, NEG);
    submax_value.assign(N, NEG);

    solve_centroid(0);

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