結果

問題 No.1098 LCAs
ユーザー Strorkis
提出日時 2020-06-26 23:05:08
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 405 ms / 2,000 ms
コード長 1,395 bytes
コンパイル時間 12,963 ms
コンパイル使用メモリ 402,624 KB
実行使用メモリ 43,840 KB
最終ジャッジ日時 2024-07-04 23:30:23
合計ジャッジ時間 19,562 ms
ジャッジサーバーID
(参考情報)
judge3 / judge5
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

struct DFS {
g: Vec<Vec<usize>>,
check: Vec<bool>,
ans: Vec<usize>,
}
impl DFS {
fn new(n: usize) -> DFS {
DFS {
g: vec![vec![]; n],
check: vec![false; n],
ans: vec![0; n],
}
}
fn search(&mut self, from: usize) -> usize {
self.check[from] = true;
let mut sum = 0;
for &to in self.g[from].clone().iter() {
if self.check[to] { continue; }
let res = self.search(to);
self.ans[from] += sum * res;
sum += res;
}
self.ans[from] *= 2;
self.ans[from] += sum * 2 + 1;
sum + 1
}
}
fn main() {
let n: usize = {
let mut buf = String::new();
std::io::stdin().read_line(&mut buf).unwrap();
buf.trim_end().parse().unwrap()
};
let mut dfs = DFS::new(n);
for _ in 0..(n - 1) {
let (v, w): (usize, usize) = {
let mut buf = String::new();
std::io::stdin().read_line(&mut buf).unwrap();
let mut iter = buf.split_whitespace();
(
iter.next().unwrap().parse::<usize>().unwrap() - 1,
iter.next().unwrap().parse::<usize>().unwrap() - 1,
)
};
dfs.g[v].push(w);
dfs.g[w].push(v);
}
dfs.search(0);
for i in 0..n {
println!("{}", dfs.ans[i]);
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0