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

• 問題: No.3755 Root for Your Route
• ユーザー: marc2825
• 提出日時: 2026-08-19 23:12:57
• 言語: C++17 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 249 ms / 3,000 ms
• コード長: 6,755 bytes
• コンパイル時間: 983 ms
• コンパイル使用メモリ: 123,584 KB
• 実行使用メモリ: 40,432 KB
• 最終ジャッジ日時: 2026-10-02 20:59:33
• 合計ジャッジ時間: 8,873 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge2_0

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

ソースコード

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const long long INF = 4e18;
const int MAXN = 100005;

int N;
vector<long long> A;
vector<vector<int>> adj;

vector<bool> used;
vector<int> sz;
vector<long long> M;

int parent_in_c[MAXN];
int depth[MAXN];
long long S_c[MAXN];
long long val[MAXN];

struct Top2 {
    long long max1 = -INF;
    int id1 = -1;
    long long max2 = -INF;
    int id2 = -1;
    
    void add(long long val, int id) {
        if (val > max1) {
            if (id != id1) {
                max2 = max1;
                id2 = id1;
            }
            max1 = val;
            id1 = id;
        } else if (val > max2 && id != id1) {
            max2 = val;
            id2 = id;
        }
    }
};

struct Line {
    long long a, b;
    long long eval(long long x) const { return a * x + b; }
};

Line tree[MAXN * 4];
vector<pair<int, Line>> history;
vector<vector<Line>> seg;

void init_lct(int node, int l, int r) {
    tree[node] = {0, -INF};
    if (l == r) return;
    int mid = l + (r - l) / 2;
    init_lct(2 * node, l, mid);
    init_lct(2 * node + 1, mid + 1, r);
}

void add_line_lct(int node, int l, int r, Line line) {
    int mid = l + (r - l) / 2;
    bool l_better = line.eval(l) > tree[node].eval(l);
    bool mid_better = line.eval(mid) > tree[node].eval(mid);
    
    if (mid_better) {
        history.push_back({node, tree[node]});
        swap(tree[node], line);
    }
    
    if (l == r) return;
    
    if (l_better != mid_better) {
        add_line_lct(2 * node, l, mid, line);
    } else {
        add_line_lct(2 * node + 1, mid + 1, r, line);
    }
}

long long query_lct(int node, int l, int r, long long x) {
    long long res = tree[node].eval(x);
    if (l == r) return res;
    int mid = l + (r - l) / 2;
    if (x <= mid) {
        return max(res, query_lct(2 * node, l, mid, x));
    } else {
        return max(res, query_lct(2 * node + 1, mid + 1, r, x));
    }
}

void add_to_seg(int node, int l, int r, int ql, int qr, Line line) {
    if (ql > r || qr < l) return;
    if (ql <= l && r <= qr) {
        seg[node].push_back(line);
        return;
    }
    int mid = l + (r - l) / 2;
    add_to_seg(2 * node, l, mid, ql, qr, line);
    add_to_seg(2 * node + 1, mid + 1, r, ql, qr, line);
}

void dfs_seg(int node, int l, int r, int D_max, const vector<vector<int>>& subtrees, int c, long long& c_max) {
    int hist_size = history.size();
    for (const Line& line : seg[node]) {
        add_line_lct(1, 1, D_max, line);
    }
    
    if (l == r) {
        int i = l;
        for (int x : subtrees[i]) {
            long long U = S_c[x] - (long long)depth[x] * (depth[x] + 1) / 2;
            long long F_val = query_lct(1, 1, D_max, depth[x]);
            if (F_val > -INF / 2) {
                long long E = U + F_val - A[c];
                val[x] = E;
                c_max = max(c_max, E);
            } else {
                val[x] = -INF;
            }
        }
    } else {
        int mid = l + (r - l) / 2;
        dfs_seg(2 * node, l, mid, D_max, subtrees, c, c_max);
        dfs_seg(2 * node + 1, mid + 1, r, D_max, subtrees, c, c_max);
    }
    
    while ((int)history.size() > hist_size) {
        auto p = history.back();
        history.pop_back();
        tree[p.first] = p.second;
    }
}

int get_sz(int u, int p) {
    sz[u] = 1;
    for (int v : adj[u]) {
        if (v != p && !used[v]) {
            sz[u] += get_sz(v, u);
        }
    }
    return sz[u];
}

int get_centroid(int u, int p, int total) {
    for (int v : adj[u]) {
        if (v != p && !used[v] && sz[v] > total / 2) {
            return get_centroid(v, u, total);
        }
    }
    return u;
}

void get_sub(int u, int p, int d, long long S, vector<int>& nodes) {
    parent_in_c[u] = p;
    depth[u] = d;
    S_c[u] = S + A[u];
    nodes.push_back(u);
    for (int v : adj[u]) {
        if (v != p && !used[v]) {
            get_sub(v, u, d + 1, S_c[u], nodes);
        }
    }
}

void decompose(int u) {
    int total = get_sz(u, -1);
    int c = get_centroid(u, -1, total);
    used[c] = true;
    
    int D_max = 0;
    vector<vector<int>> subtrees;
    for (int v : adj[c]) {
        if (!used[v]) {
            vector<int> nodes;
            get_sub(v, c, 1, A[c], nodes);
            subtrees.push_back(nodes);
            for(int x : nodes) {
                D_max = max(D_max, depth[x]);
            }
        }
    }
    
    int K = subtrees.size();
    if (K > 0) {
        vector<Top2> top2(D_max + 1);
        top2[0].add(A[c], -1);
        
        for (int i = 0; i < K; ++i) {
            for (int x : subtrees[i]) {
                long long W = S_c[x] - (long long)depth[x] * (depth[x] + 1) / 2;
                top2[depth[x]].add(W, i);
            }
        }
        
        seg.assign(4 * K, vector<Line>());
        history.clear();
        init_lct(1, 1, D_max);
        
        add_to_seg(1, 0, K - 1, 0, K - 1, {0, A[c]});
        for (int d = 1; d <= D_max; ++d) {
            if (top2[d].max1 != -INF) {
                int id1 = top2[d].id1;
                add_to_seg(1, 0, K - 1, 0, id1 - 1, {-d, top2[d].max1});
                add_to_seg(1, 0, K - 1, id1 + 1, K - 1, {-d, top2[d].max1});
                
                if (top2[d].max2 != -INF) {
                    add_to_seg(1, 0, K - 1, id1, id1, {-d, top2[d].max2});
                }
            }
        }
        
        long long c_max = -INF;
        dfs_seg(1, 0, K - 1, D_max, subtrees, c, c_max);
        
        for (int i = 0; i < K; ++i) {
            for (int j = (int)subtrees[i].size() - 1; j >= 0; --j) {
                int x = subtrees[i][j];
                if (parent_in_c[x] != c) {
                    val[parent_in_c[x]] = max(val[parent_in_c[x]], val[x]);
                }
                M[x] = max(M[x], val[x]);
            }
        }
        M[c] = max({M[c], c_max, (long long)A[c]});
    } else {
        M[c] = max(M[c], (long long)A[c]);
    }
    
    for (int v : adj[c]) {
        if (!used[v]) {
            decompose(v);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    if (!(cin >> N)) return 0;
    
    A.resize(N + 1);
    for (int i = 1; i <= N; ++i) {
        cin >> A[i];
    }
    
    adj.resize(N + 1);
    for (int i = 0; i < N - 1; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    used.assign(N + 1, false);
    sz.resize(N + 1);
    M.assign(N + 1, -INF);
    for (int i = 1; i <= N; ++i) {
        M[i] = A[i];
    }
    
    decompose(1);
    
    long long ans = INF;
    for (int i = 1; i <= N; ++i) {
        ans = min(ans, M[i]);
    }
    cout << ans << "\n";
    
    return 0;
}