#1181368 (Rust) No.3660 LIS on Tree

• 問題: No.3660 LIS on Tree
• ユーザー: NakLon131
• 提出日時: 2026-08-30 15:39:24
• 言語: Rust (1.97.1 + proconio + num + itertools)
• 結果: AC
• 実行時間: 57 ms / 2,000 ms
• コード長: 3,618 bytes
• コンパイル時間: 1,691 ms
• コンパイル使用メモリ: 196,544 KB
• 実行使用メモリ: 20,000 KB
• 最終ジャッジ日時: 2026-08-30 15:39:28
• 合計ジャッジ時間: 3,584 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge1_0

ファイルパターン	結果
sample	AC * 3
other	AC * 20

ソースコード

fn main() {
    input! {
        n: usize,
        s: [i64; n],
        ab: [(Usize1, Usize1); n-1],
    }

    // 高い方へ遷移する有向グラフを作る
    let graph = make_directed_graph(n, &s, &ab);

    // 木DP
    let mut dp = vec![-INF; n];
    let mut seen = vec![false; n];

    // dfs
    for spos in 0..n {
        if seen[spos] { continue; }
        dfs(spos, &s, &graph, &mut seen, &mut dp);
    }

    let mut ans = -INF;
    for &val in &dp {
        ans = max(ans, val);
    }
    println!("{}", ans);
}

fn dfs(
    pos: usize,
    s: &Vec<i64>, graph: &Vec<Vec<usize>>,
    seen: &mut Vec<bool>, dp: &mut Vec<i64>,
) {
    seen[pos] = true;

    // 部分木からmaxをもらう
    let mut ret = 0;
    for &npos in &graph[pos] {
        if !seen[npos] { 
            dfs(npos, s, graph, seen, dp);
        }
        let get_val = dp[npos];
        ret = max(ret, get_val);
    }

    ret += s[pos];
    dp[pos] = ret;
}

fn make_directed_graph(
    n: usize, s: &Vec<i64>, ab: &Vec<(usize, usize)>
) -> Vec<Vec<usize>> {
    let mut graph = vec![Vec::new(); n];
    for &(a, b) in ab {
        if s[a] < s[b] { graph[a].push(b); }
        if s[a] > s[b] { graph[b].push(a); }
    }
    graph
}

// const MOD93: usize = 998244353;
// const MOD17: usize = 1000000007;
// const INV2: usize = 499122177; // MOD93の剰余世界では、1/2の代わりにこれを掛ける
const INF: i64 = 1 << 60;
// const D: [(usize, usize); 4] = [(!0, 0), (0, !0), (1, 0), (0, 1)]; // 上左下右
// fn us(x: i32) -> usize { x as usize }

// 文字の定義
// const CHAR_SZ: usize = 26;
// const UPPER_A_ASCII : usize = 0x41;
// const UPPER_Z_ASCII : usize = UPPER_A_ASCII + SZ - 1;
// const LOWER_A_ASCII : usize = 0x61;
// const LOWER_Z_ASCII : usize = LOWER_A_ASCII + SZ - 1;
#[allow(unused)]
#[derive(PartialEq, Eq, PartialOrd, Ord, Hash, Clone)]
struct Pos {
    x: usize,
    y: usize,
}
#[allow(unused)]
enum Direction {
    UP = 0,
    LEFT = 1,
    DOWN = 2,
    RIGHT = 3,
}
#[allow(unused)]
#[derive(PartialEq, Eq, PartialOrd, Ord, Hash, Clone)]
struct LoopCount {
    ans: usize, // 答え
    step: usize, // 残りステップ
    pos: usize, // 現在位置
    cycle_len: usize, // サイクル数
    cycle_add: usize, // サイクルによる増加
}
#[allow(unused)]
use proconio::{input, marker::Chars, marker::Usize1};
// use proconio::{input, input_interactive, marker::Chars, marker::Usize1};

#[allow(unused)]
use std::{
    println, print,
    mem::swap,
    cmp::min, cmp::max,
    cmp::Reverse,
    collections::HashSet, collections::BTreeSet,
    collections::HashMap, collections::BTreeMap,
    collections::BinaryHeap,
    collections::VecDeque,
    iter::FromIterator,
};
#[allow(unused)]
use itertools::Itertools;
// #[allow(unused)]
// use num::{integer::gcd, Signed};
// #[allow(unused)]
// use num_integer::Roots;// 通常の平方根
// #[allow(unused)]
// use superslice::Ext;
// #[allow(unused)]
// use rand::Rng;
// let mut rng = rand::thread_rng();
// let n = rng.gen_range(1, 1000);

// 連想配列のデバッグ
#[allow(unused)]
fn dbg_print_mp(mp: &HashMap<usize, usize>) {
    for (&k, &v) in mp { println!("key:{} val:{}", k, v); }
}
// グリッドのデバッグ
#[allow(unused)]
fn dbg_print_grid(h: usize, w: usize, grid: &Vec<Vec<char>>) {
    for i in 0..h { for j in 0..w { print!("{}", grid[i][j]); } println!(); }
}
// 最短距離のデバッグ
#[allow(unused)]
fn dbg_print_dist(h: usize, w: usize, dist: &Vec<Vec<usize>>) {
    let limit = 255;
    for i in 0..h { for j in 0..w { print!("{:03} ", min(dist[i][j], limit)); } println!(); }
}