結果
問題 |
No.763 Noelちゃんと木遊び
|
ユーザー |
|
提出日時 | 2025-07-13 10:31:33 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 40 ms / 2,000 ms |
コード長 | 1,561 bytes |
コンパイル時間 | 15,173 ms |
コンパイル使用メモリ | 397,276 KB |
実行使用メモリ | 21,120 KB |
最終ジャッジ日時 | 2025-07-13 10:31:50 |
合計ジャッジ時間 | 11,565 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 22 |
ソースコード
// #[rustfmt::skip] // pub mod lib {pub use ac_library::*;pub use itertools::{join, Combinations, Itertools, MultiProduct, Permutations};pub use proconio::{input,marker::{Chars, Usize1}};pub use std::{cmp::*, collections::*, mem::swap};pub use regex::Regex;pub use superslice::Ext;pub use num_traits::{One, ToPrimitive, FromPrimitive, PrimInt};#[macro_export]macro_rules! degg {($($val:expr),+ $(,)?) => {println!("[{}:{}] {}",file!(),line!(),{let mut parts = Vec::new();$(parts.push(format!("{} = {:?}", stringify!($val), &$val));)+parts.join(", ")})}}} // use lib::*; use std::cmp::max; use proconio::{input, marker::Usize1}; fn dfs(v: usize, to: &Vec<Vec<usize>>, p: usize, dp: &mut Vec<(usize, usize)>) -> (usize, usize) { if dp[v] != (usize::MAX, usize::MAX) { return dp[v] } let mut is_leaf = true; let mut kesu = 0; let mut nokosu = 0; for &v2 in to[v].iter() { if p == v2 { continue; } is_leaf = false; let pre = dfs(v2, to, v, dp); kesu += max(pre.0, pre.1); nokosu += max(pre.0, pre.1 - 1); } if is_leaf { dp[v] = (0, 1); return dp[v] } dp[v] = (kesu, nokosu + 1); dp[v] } fn main() { input! { n: usize, uv: [(Usize1, Usize1); n - 1] } let mut to = vec![vec![]; n]; for &(u, v) in uv.iter() { to[u].push(v); to[v].push(u); } let mut dp = vec![(usize::MAX, usize::MAX); n]; let ans = dfs(0, &to, usize::MAX, &mut dp); println!("{}", max(ans.0, ans.1)); }