結果

問題 No.763 Noelちゃんと木遊び
ユーザー ngtkanangtkana
提出日時 2024-06-11 11:52:10
言語 Rust
(1.77.0 + proconio)
結果
AC  
実行時間 32 ms / 2,000 ms
コード長 2,396 bytes
コンパイル時間 15,888 ms
コンパイル使用メモリ 382,956 KB
実行使用メモリ 14,848 KB
最終ジャッジ日時 2024-06-11 11:52:29
合計ジャッジ時間 15,160 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 21 ms
14,848 KB
testcase_01 AC 10 ms
6,528 KB
testcase_02 AC 23 ms
12,160 KB
testcase_03 AC 17 ms
8,832 KB
testcase_04 AC 12 ms
7,040 KB
testcase_05 AC 16 ms
8,704 KB
testcase_06 AC 32 ms
14,336 KB
testcase_07 AC 30 ms
13,824 KB
testcase_08 AC 18 ms
9,216 KB
testcase_09 AC 12 ms
6,784 KB
testcase_10 AC 4 ms
5,376 KB
testcase_11 AC 32 ms
14,720 KB
testcase_12 AC 27 ms
13,184 KB
testcase_13 AC 25 ms
12,928 KB
testcase_14 AC 23 ms
11,776 KB
testcase_15 AC 15 ms
8,832 KB
testcase_16 AC 4 ms
5,376 KB
testcase_17 AC 16 ms
8,960 KB
testcase_18 AC 31 ms
14,336 KB
testcase_19 AC 29 ms
13,184 KB
testcase_20 AC 27 ms
13,056 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

use proconio::input;
use proconio::marker::Usize1;

fn main() {
    input! {
        n: usize,
        edges: [(Usize1, Usize1); n - 1],
    }
    let mut g = vec![Vec::new(); n];
    for &(i, j) in &edges {
        g[i].push(j);
        g[j].push(i);
    }
    let mut sorted = Vec::new();
    let mut parent = vec![usize::MAX; n];
    let mut stack = vec![0];
    while let Some(i) = stack.pop() {
        sorted.push(i);
        g[i].retain(|&j| j != parent[i]);
        for &j in &g[i] {
            stack.push(j);
            parent[j] = i;
        }
    }

    let dp = tree_dp(&O {}, &g, &sorted);
    let ans = dp[0].retain.max(dp[0].remove);
    println!("{ans}");
}

#[derive(Debug, Clone, PartialEq, Default)]
struct Value {
    retain: usize,
    remove: usize,
}

#[derive(Debug, Clone, PartialEq, Default)]
struct Acc {
    any_sum: usize,
    remove_sum: usize,
}

struct O {}
impl Op for O {
    type Acc = Acc;
    type Value = Value;

    fn f(&self, value: &Self::Value, _index: usize) -> Self::Acc {
        Self::Acc {
            any_sum: value.retain.max(value.remove),
            remove_sum: value.remove,
        }
    }

    fn mul(&self, lhs: &Self::Acc, rhs: &Self::Acc, _parent: usize) -> Self::Acc {
        Self::Acc {
            any_sum: lhs.any_sum + rhs.any_sum,
            remove_sum: lhs.remove_sum + rhs.remove_sum,
        }
    }

    fn identity(&self, _parent: usize) -> Self::Acc {
        Self::Acc {
            any_sum: 0,
            remove_sum: 0,
        }
    }

    fn g(&self, acc: &Self::Acc, _index: usize) -> Self::Value {
        Self::Value {
            retain: 1 + acc.remove_sum,
            remove: acc.any_sum,
        }
    }
}

pub trait Op {
    type Value: Default + Clone;
    type Acc: Default + Clone;

    fn f(&self, value: &Self::Value, index: usize) -> Self::Acc;
    fn mul(&self, lhs: &Self::Acc, rhs: &Self::Acc, parent: usize) -> Self::Acc;
    fn identity(&self, parent: usize) -> Self::Acc;
    fn g(&self, acc: &Self::Acc, index: usize) -> Self::Value;
}

pub fn tree_dp<O: Op>(o: &O, g: &[Vec<usize>], sorted: &[usize]) -> Vec<O::Value> {
    let mut dp = vec![O::Value::default(); g.len()];
    for &i in sorted.iter().rev() {
        dp[i] = o.g(
            &g[i]
                .iter()
                .fold(o.identity(i), |acc, &j| o.mul(&acc, &o.f(&dp[j], j), i)),
            i,
        );
    }
    dp
}
0