結果

問題 No.763 Noelちゃんと木遊び
コンテスト
ユーザー ngtkana
提出日時 2024-06-10 16:33:44
言語 Rust
(1.94.0 + proconio + num + itertools)
コンパイル:
/usr/bin/rustc_custom
実行:
./target/release/main
結果
AC  
実行時間 25 ms / 2,000 ms
コード長 1,736 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 741 ms
コンパイル使用メモリ 206,252 KB
実行使用メモリ 13,952 KB
最終ジャッジ日時 2026-07-07 19:53:46
合計ジャッジ時間 2,665 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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 o = O {};
    let mut dp = vec![Value::default(); n];
    for &i in sorted.iter().rev() {
        dp[i] = o.g(g[i]
            .iter()
            .fold(O::identity(), |acc, &j| O::mul(acc, o.f(dp[j]))));
    }
    let ans = dp[0].x.max(dp[0].y);
    println!("{ans}");
}

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

    fn f(&self, value: Value) -> Acc {
        Acc {
            a: value.x.max(value.y),
            b: value.x,
        }
    }

    fn g(&self, acc: Acc) -> Value {
        Value {
            x: acc.a,
            y: 1 + acc.b,
        }
    }

    fn identity() -> Acc {
        Acc { a: 0, b: 0 }
    }

    fn mul(lhs: Acc, rhs: Acc) -> Acc {
        Acc {
            a: lhs.a + rhs.a,
            b: lhs.b + rhs.b,
        }
    }
}

#[derive(Debug, Clone, Copy, PartialEq, Default)]
struct Value {
    x: usize,
    y: usize,
}

#[derive(Debug, Clone, Copy, PartialEq, Default)]
struct Acc {
    a: usize,
    b: usize,
}

trait Op {
    type Value;
    type Acc;

    fn f(&self, value: Value) -> Acc;

    fn g(&self, acc: Acc) -> Value;

    fn identity() -> Acc;

    fn mul(lhs: Acc, rhs: Acc) -> Acc;
}
0