結果
問題 |
No.1418 Sum of Sum of Subtree Size
|
ユーザー |
|
提出日時 | 2021-03-05 23:30:05 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 54 ms / 2,000 ms |
コード長 | 1,386 bytes |
コンパイル時間 | 13,647 ms |
コンパイル使用メモリ | 402,608 KB |
実行使用メモリ | 20,736 KB |
最終ジャッジ日時 | 2024-10-07 05:26:16 |
合計ジャッジ時間 | 16,048 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 41 |
ソースコード
use std::io::*; // 0を根とした各部分木のサイズ fn dfs1(v: usize, p: usize, sz: &mut Vec<usize>, g: &Vec<Vec<usize>>) -> usize { for &nv in g[v].iter() { if nv != p { sz[v] += dfs1(nv, v, sz, &g); } } sz[v] } // vを根とした状態になってる fn dfs2(v: usize, p: usize, sz: &mut Vec<usize>, ans: &mut Vec<usize>, g: &Vec<Vec<usize>>) { for &nv in g[v].iter() { ans[v] += (g.len() - sz[nv]) * sz[nv]; } for &nv in g[v].iter() { if nv != p { sz[v] -= sz[nv]; sz[nv] += sz[v]; dfs2(nv, v, sz, ans, &g); sz[nv] -= sz[v]; sz[v] += sz[nv]; } } } fn main() { let mut s: String = String::new(); std::io::stdin().read_to_string(&mut s).ok(); let mut itr = s.trim().split_whitespace(); let n: usize = itr.next().unwrap().parse().unwrap(); let mut g: Vec<Vec<usize>> = vec![Vec::new(); n]; for _ in 0..n - 1 { let a: usize = itr.next().unwrap().parse::<usize>().unwrap() - 1; let b: usize = itr.next().unwrap().parse::<usize>().unwrap() - 1; g[a].push(b); g[b].push(a); } let mut ans = vec![0; n]; let mut size = vec![1; n]; dfs1(0, 0, &mut size, &g); dfs2(0, 0, &mut size, &mut ans, &g); let s: usize = ans.iter().sum(); println!("{}", s + n * n); }