結果
問題 | No.1418 Sum of Sum of Subtree Size |
ユーザー |
|
提出日時 | 2022-11-23 00:59:29 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 61 ms / 2,000 ms |
コード長 | 1,009 bytes |
コンパイル時間 | 13,270 ms |
コンパイル使用メモリ | 378,940 KB |
実行使用メモリ | 22,016 KB |
最終ジャッジ日時 | 2024-09-23 07:44:41 |
合計ジャッジ時間 | 15,684 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 41 |
ソースコード
fn dfs(cur: usize, prev: usize, paths: &Vec<Vec<(usize, usize)>>, lines: &mut Vec<usize>) -> usize {let mut ret = 1usize;for &(v, idx) in paths[cur].iter() {if v == prev { continue; }let val = dfs(v, cur, paths, lines) ;lines[idx] = val;ret += val;}ret}fn main() {let mut n = String::new();std::io::stdin().read_line(&mut n).ok();let n: usize = n.trim().parse().unwrap();let mut paths = vec![vec![]; n];for i in 0..n-1 {let mut ab = String::new();std::io::stdin().read_line(&mut ab).ok();let ab: Vec<usize> = ab.trim().split_whitespace().map(|s| s.parse().unwrap()).collect();let a = ab[0]-1;let b = ab[1]-1;paths[a].push((b, i));paths[b].push((a, i));}let mut lines = vec![0usize; n-1];dfs(0, 0, &paths, &mut lines);let mut result = n * n;for &v in lines.iter() {result += (n - v) * v * 2;}println!("{}", result);}