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

• 問題: No.3755 Root for Your Route
• ユーザー: marc2825
• 提出日時: 2026-08-19 23:11:22
• 言語: C++17 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 422 ms / 3,000 ms
• コード長: 5,824 bytes
• コンパイル時間: 1,364 ms
• コンパイル使用メモリ: 228,128 KB
• 実行使用メモリ: 21,244 KB
• 最終ジャッジ日時: 2026-10-02 20:59:24
• 合計ジャッジ時間: 13,416 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge2_0

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

ソースコード

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
static const ll NEG = LLONG_MIN / 4;

struct Line { ll m, b; };
static inline ll ev(const Line& L, ll x) { return L.m * x + L.b; }

int N, LCN, curStamp = 0;
vector<int> head_, nxt_, to_;
vector<ll> A, Sum_, X_, best_, g_, ans_;
vector<int> sz_, par_, dep_;
vector<char> rem_;
vector<Line> lc; vector<int> stmp;
vector<int> comp_, bst_;

void lcInsert(Line nw) {
    int node = 1, l = 0, r = LCN;
    while (true) {
        if (stmp[node] != curStamp) { stmp[node] = curStamp; lc[node] = nw; return; }
        int mid = l + (r - l) / 2;
        bool lef = ev(nw, l) > ev(lc[node], l);
        bool mi  = ev(nw, mid) > ev(lc[node], mid);
        if (mi) swap(lc[node], nw);
        if (l == r) return;
        if (lef != mi) { node = node * 2; r = mid; }
        else { node = node * 2 + 1; l = mid + 1; }
    }
}
ll lcQuery(ll x) {
    int node = 1, l = 0, r = LCN; ll res = NEG;
    while (true) {
        if (stmp[node] == curStamp) res = max(res, ev(lc[node], x));
        if (l == r) break;
        int mid = l + (r - l) / 2;
        if (x <= mid) { node = node * 2; r = mid; }
        else { node = node * 2 + 1; l = mid + 1; }
    }
    return res;
}

void process(int c) {
    comp_.clear(); bst_.clear();
    par_[c] = 0; dep_[c] = 0; Sum_[c] = A[c]; X_[c] = A[c];
    comp_.push_back(c);
    for (int e = head_[c]; e != -1; e = nxt_[e]) {
        int u = to_[e];
        if (rem_[u]) continue;
        bst_.push_back((int)comp_.size());
        par_[u] = c; dep_[u] = 1; Sum_[u] = A[c] + A[u]; X_[u] = Sum_[u] - 1;
        int st = (int)comp_.size();
        comp_.push_back(u);
        for (int i = st; i < (int)comp_.size(); i++) {
            int v = comp_[i];
            for (int e2 = head_[v]; e2 != -1; e2 = nxt_[e2]) {
                int w = to_[e2];
                if (w == par_[v] || rem_[w]) continue;
                par_[w] = v; dep_[w] = dep_[v] + 1;
                Sum_[w] = Sum_[v] + A[w];
                X_[w] = Sum_[w] - (ll)dep_[w] * (dep_[w] + 1) / 2;
                comp_.push_back(w);
            }
        }
    }
    bst_.push_back((int)comp_.size());
    int K = (int)bst_.size() - 1;

    ll maxX = NEG;
    for (int v : comp_) maxX = max(maxX, X_[v]);
    for (size_t i = 1; i < comp_.size(); i++) best_[comp_[i]] = A[c]; // w = c (片腕のみ)

    curStamp++;                                   // prefix 方向
    for (int k = 0; k < K; k++) {
        for (int i = bst_[k]; i < bst_[k + 1]; i++) {
            int v = comp_[i]; ll q = lcQuery(dep_[v]);
            if (q > best_[v]) best_[v] = q;
        }
        for (int i = bst_[k]; i < bst_[k + 1]; i++) {
            int v = comp_[i]; lcInsert(Line{ -(ll)dep_[v], X_[v] });
        }
    }
    curStamp++;                                   // suffix 方向
    for (int k = K - 1; k >= 0; k--) {
        for (int i = bst_[k]; i < bst_[k + 1]; i++) {
            int v = comp_[i]; ll q = lcQuery(dep_[v]);
            if (q > best_[v]) best_[v] = q;
        }
        for (int i = bst_[k]; i < bst_[k + 1]; i++) {
            int v = comp_[i]; lcInsert(Line{ -(ll)dep_[v], X_[v] });
        }
    }

    g_[c] = maxX;
    for (size_t i = 1; i < comp_.size(); i++) {
        int v = comp_[i];
        g_[v] = X_[v] + best_[v] - A[c];
    }
    for (int i = (int)comp_.size() - 1; i >= 1; i--) {   // 部分木 max
        int v = comp_[i], p = par_[v];
        if (g_[v] > g_[p]) g_[p] = g_[v];
    }
    for (int v : comp_) if (g_[v] > ans_[v]) ans_[v] = g_[v];
}

static int rdchar() { return getchar_unlocked(); }
static ll readInt() {
    int c = rdchar(); while (c != '-' && (c < '0' || c > '9')) c = rdchar();
    int sg = 1; if (c == '-') { sg = -1; c = rdchar(); }
    ll x = 0; while (c >= '0' && c <= '9') { x = x * 10 + (c - '0'); c = rdchar(); }
    return x * sg;
}

int main() {
    N = (int)readInt();
    A.assign(N + 1, 0);
    for (int i = 1; i <= N; i++) A[i] = readInt();
    head_.assign(N + 1, -1);
    nxt_.assign(2 * (N - 1), -1); to_.assign(2 * (N - 1), 0);
    int cnt = 0;
    for (int i = 0; i < N - 1; i++) {
        int u = (int)readInt(), v = (int)readInt();
        to_[cnt] = v; nxt_[cnt] = head_[u]; head_[u] = cnt++;
        to_[cnt] = u; nxt_[cnt] = head_[v]; head_[v] = cnt++;
    }
    Sum_.assign(N + 1, 0); X_.assign(N + 1, 0); best_.assign(N + 1, 0);
    g_.assign(N + 1, NEG); ans_.assign(N + 1, NEG);
    sz_.assign(N + 1, 0); par_.assign(N + 1, 0); dep_.assign(N + 1, 0);
    rem_.assign(N + 1, 0);
    LCN = N; lc.assign(4 * (N + 2), Line{0, 0}); stmp.assign(4 * (N + 2), -1);

    vector<int> stk, ord; stk.push_back(1);
    while (!stk.empty()) {
        int s = stk.back(); stk.pop_back();
        ord.clear(); par_[s] = 0; ord.push_back(s);
        for (size_t i = 0; i < ord.size(); i++) {
            int v = ord[i];
            for (int e = head_[v]; e != -1; e = nxt_[e]) {
                int u = to_[e];
                if (u == par_[v] || rem_[u]) continue;
                par_[u] = v; ord.push_back(u);
            }
        }
        int tot = (int)ord.size();
        for (int v : ord) sz_[v] = 1;
        for (int i = tot - 1; i >= 1; i--) sz_[par_[ord[i]]] += sz_[ord[i]];
        int c = ord[0];
        for (int v : ord) {
            int mx = tot - sz_[v];
            for (int e = head_[v]; e != -1; e = nxt_[e]) {
                int u = to_[e];
                if (u == par_[v] || rem_[u]) continue;
                mx = max(mx, sz_[u]);
            }
            if (mx * 2 <= tot) { c = v; break; }
        }
        process(c);
        rem_[c] = 1;
        for (int e = head_[c]; e != -1; e = nxt_[e])
            if (!rem_[to_[e]]) stk.push_back(to_[e]);
    }
    ll res = LLONG_MAX;
    for (int v = 1; v <= N; v++) res = min(res, ans_[v]);
    printf("%lld\n", res);
    return 0;
}