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

• 問題: No.3755 Root for Your Route
• ユーザー: marc2825
• 提出日時: 2026-08-19 23:11:07
• 言語: C++17 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 294 ms / 3,000 ms
• コード長: 7,521 bytes
• コンパイル時間: 1,747 ms
• コンパイル使用メモリ: 246,908 KB
• 実行使用メモリ: 19,196 KB
• 最終ジャッジ日時: 2026-10-02 20:59:30
• 合計ジャッジ時間: 11,299 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge4_1

ファイルパターン	結果
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 m = 0;
    ll b = NEG;

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

// maximum Li Chao Tree
struct LiChao {
    int X;
    vector<Line> seg;

    LiChao(int xmax = 0) {
        init(xmax);
    }

    void init(int xmax) {
        X = max(0, xmax);
        seg.assign(4 * (X + 1) + 5, Line{});
    }

    void clear() {
        fill(seg.begin(), seg.end(), Line{});
    }

    void add_line(Line nw) {
        add_line(nw, 1, 0, X);
    }

    void add_line(Line nw, int k, int l, int r) {
        if (seg[k].b == NEG) {
            seg[k] = nw;
            return;
        }

        int mid = (l + r) / 2;

        bool left_better = nw.get(l) > seg[k].get(l);
        bool mid_better  = nw.get(mid) > seg[k].get(mid);

        if (mid_better) {
            swap(nw, seg[k]);
        }

        if (l == r) return;

        if (left_better != mid_better) {
            add_line(nw, k * 2, l, mid);
        } else {
            add_line(nw, k * 2 + 1, mid + 1, r);
        }
    }

    ll query(int x) const {
        return query(x, 1, 0, X);
    }

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

        if (l == r) return res;

        int mid = (l + r) / 2;

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

struct Info {
    int v;
    int parent;
    int depth;
    ll B;
};

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

vector<int> sub;
vector<int> par;
vector<char> dead;

// ans[r] = r を通るパスの最大スコア
vector<ll> ans;

// 重心処理用
vector<ll> otherBest;
vector<ll> cur;


// 現在の連結成分の重心を探す
int get_centroid(int start) {
    vector<int> order;
    vector<int> st;

    st.push_back(start);
    par[start] = -1;

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

        order.push_back(u);

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

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

    // subtree size
    for (int i = (int)order.size() - 1; i >= 0; --i) {
        int u = order[i];

        sub[u] = 1;

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

            if (par[v] == u) {
                sub[u] += sub[v];
            }
        }
    }

    int total = order.size();

    for (int u : order) {
        int mx = total - sub[u];

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

            if (par[v] == u) {
                mx = max(mx, sub[v]);
            }
        }

        if (mx * 2 <= total) {
            return u;
        }
    }

    assert(false);
    return -1;
}


// 重心 c の隣接成分を収集
vector<Info> collect_component(int c, int first) {
    vector<Info> res;

    struct State {
        int u;
        int p;
        int d;
        ll sum;
    };

    vector<State> st;

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

    while (!st.empty()) {
        auto [u, p, d, sum] = st.back();
        st.pop_back();

        ll tri = 1LL * d * (d + 1) / 2;

        // B_u
        ll B = sum - tri;

        res.push_back({
            u,
            p,
            d,
            B
        });

        for (int v : G[u]) {
            if (dead[v] || v == p) continue;

            st.push_back({
                v,
                u,
                d + 1,
                sum + A[v]
            });
        }
    }

    return res;
}


void process_centroid(int c) {
    vector<vector<Info>> comps;

    int maxDepth = 0;

    // c を消したあとの各連結成分
    for (int v : G[c]) {
        if (dead[v]) continue;

        auto vec = collect_component(c, v);

        for (auto &e : vec) {
            maxDepth = max(maxDepth, e.depth);
        }

        comps.push_back(move(vec));
    }

    // s=t=c
    ans[c] = max(ans[c], A[c]);

    if (comps.empty()) return;

    LiChao hull(maxDepth);

    /*
        y = c も候補にする。

        d_c = 0
        B_c = A_c

        よって直線は
        y = A_c
    */
    hull.add_line({0, A[c]});

    /*
        左 -> 右

        現在の component より前の component だけが
        Li Chao Tree に入っている。
    */
    for (auto &comp : comps) {

        for (auto &x : comp) {

            ll q = hull.query(x.depth);

            otherBest[x.v] = q;

            // B_x + max(B_y - d_x d_y) - A_c
            ll score = x.B - A[c] + q;

            // このパスは c を通る
            ans[c] = max(ans[c], score);
        }

        // query の後に追加することで
        // 同じ component 同士を選ばない
        for (auto &x : comp) {
            hull.add_line({
                -x.depth,
                x.B
            });
        }
    }


    /*
        右 -> 左

        反対側の component も候補にする。
    */
    hull.clear();
    hull.add_line({0, A[c]});

    for (int i = (int)comps.size() - 1; i >= 0; --i) {

        auto &comp = comps[i];

        for (auto &x : comp) {

            ll q = hull.query(x.depth);

            otherBest[x.v] =
                max(otherBest[x.v], q);
        }

        for (auto &x : comp) {
            hull.add_line({
                -x.depth,
                x.B
            });
        }
    }


    /*
        r がある component 内に存在するとする。

        c を通るパスが r も通るためには、
        component 側の端点 x が
        c を根とした r の部分木内にあればよい。

        よって

            cur[x]
              = x を端点にしたときの最良値

        を部分木 maximum にする。
    */
    for (auto &comp : comps) {

        for (auto &x : comp) {

            cur[x.v]
                = x.B
                - A[c]
                + otherBest[x.v];
        }

        /*
            collect_component では親が子より先に入るので、
            reverse すれば postorder。
        */
        for (int i = (int)comp.size() - 1; i >= 0; --i) {

            auto &x = comp[i];

            // x.v の部分木から端点を選ぶ
            ans[x.v] =
                max(ans[x.v], cur[x.v]);

            // 親へ部分木 maximum を伝える
            if (x.parent != c) {
                cur[x.parent] =
                    max(cur[x.parent], cur[x.v]);
            }
        }
    }
}


// centroid decomposition
void decompose(int start) {

    int c = get_centroid(start);

    process_centroid(c);

    dead[c] = true;

    for (int v : G[c]) {

        if (!dead[v]) {
            decompose(v);
        }
    }
}


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

    cin >> N;

    A.resize(N);

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

    G.assign(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);
    }

    sub.resize(N);
    par.resize(N);

    dead.assign(N, false);

    ans.assign(N, NEG);
    otherBest.assign(N, NEG);
    cur.assign(N, NEG);

    decompose(0);

    /*
        Bob は ans[r] を最小にする r を選ぶ。
    */
    cout << *min_element(ans.begin(), ans.end()) << '\n';
}