結果

問題 No.3660 LIS on Tree
コンテスト
ユーザー wasd314
提出日時 2026-08-30 14:52:14
言語 C++23(gcc16)
(gcc 16.1.0 + boost 1.92.0)
コンパイル:
g++-16 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 160 ms / 2,000 ms
+ 295µs
コード長 991 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,674 ms
コンパイル使用メモリ 196,184 KB
実行使用メモリ 17,912 KB
最終ジャッジ日時 2026-08-30 14:52:28
合計ジャッジ時間 5,301 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge3_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <algorithm>
#include <functional>
#include <iostream>
#include <utility>
#include <vector>
int main() {
    using namespace std;
    using lint = long long;

    int n;
    cin >> n;
    vector<lint> s(n);
    for (auto &e : s) cin >> e;

    vector g(n, vector<int>());
    for (int i = 0; i < n - 1; ++i) {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    const lint oo = 1e18;
    // [v]: v 以下

    vector dp(n, -oo);
    auto chmax = [](auto &x, auto y) { x = max(x, y); };

    auto dfs = [&](this auto self, int v) -> lint {
        if (dp[v] != -oo) return dp[v];
        lint ans = s[v];
        for (int nv : g[v]) {
            if (s[nv] > s[v]) {
                auto ansi = self(nv);
                chmax(ans, s[v] + ansi);
            }
        }
        return dp[v] = ans;
    };
    lint ans = -oo;
    for (int i = 0; i < n; ++i) chmax(ans, dfs(i));
    cout << ans << "\n";
}
0