結果
| 問題 | No.1197 モンスターショー |
| ユーザー |
 akakimidori
|
| 提出日時 | 2020-08-23 05:56:36 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 591 ms / 3,000 ms |
| コード長 | 6,595 bytes |
| コンパイル時間 | 17,494 ms |
| コンパイル使用メモリ | 377,092 KB |
| 実行使用メモリ | 31,348 KB |
| 最終ジャッジ日時 | 2024-10-15 18:37:20 |
| 合計ジャッジ時間 | 25,166 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 41 |
ソースコード
// ---------- begin Centroid Decomposition ----------struct CentroidDecomposition {graph: Vec<Vec<usize>>,next: Vec<(usize, usize)>,}#[allow(dead_code)]impl CentroidDecomposition {fn new(n: usize) -> Self {CentroidDecomposition {graph: vec![vec![]; n],next: vec![],}}fn add_edge(&mut self, a: usize, b: usize) {self.graph[a].push(b);self.graph[b].push(a);}fn build(&mut self) {let graph = &self.graph;let next = &mut self.next;let n = graph.len();next.clear();next.resize(n, (n, n));assert!(graph.iter().fold(0, |s, a| s + a.len()) == 2 * n - 2,"graph is not tree");let mut dfs = vec![(0, 0, n)];let mut used = vec![false; n];let mut size = vec![0; n];let mut stack = vec![];let mut q = vec![];while let Some((v, rank, g)) = dfs.pop() {size[v] = 0;stack.push((v, v));q.clear();while let Some((v, p)) = stack.pop() {q.push(v);for &u in graph[v].iter() {size[u] = 0;if u != p && !used[u] {stack.push((u, v));}}}for &v in q.iter().rev() {size[v] = 1;for &u in graph[v].iter() {size[v] += size[u];}}let mut parent = v;let mut r = v;loop {let mut max = (0, 0);for &u in graph[r].iter() {if u != parent && !used[u] {max = std::cmp::max(max, (size[u], u));}}if 2 * max.0 <= size[v] {break;}parent = r;r = max.1;}used[r] = true;next[r] = (rank, g);for &v in graph[r].iter() {if !used[v] {dfs.push((v, rank + 1, r));}}}}fn belong(&self, v: usize) -> Vec<usize> {let mut ans = vec![];let mut v = v;while v < self.graph.len() {ans.push(v);v = self.next[v].1;}ans}fn rank(&self, v: usize) -> usize {self.next[v].0}}// ---------- end Centroid Decomposition ----------// ---------- begin scannner ----------#[allow(dead_code)]mod scanner {use std;use std::io::Read;use std::str::FromStr;use std::str::SplitWhitespace;pub struct Scanner<'a> {it: SplitWhitespace<'a>,}impl<'a> Scanner<'a> {pub fn new(s: &'a String) -> Scanner<'a> {Scanner {it: s.split_whitespace(),}}pub fn next<T: FromStr>(&mut self) -> T {match self.it.next().unwrap().parse::<T>() {Ok(v) => v,_ => panic!("Scanner error"),}}pub fn next_chars(&mut self) -> Vec<char> {self.next::<String>().chars().collect()}pub fn next_vec<T: FromStr>(&mut self, len: usize) -> Vec<T> {(0..len).map(|_| self.next()).collect()}}pub fn read_string() -> String {let mut s = String::new();std::io::stdin().read_to_string(&mut s).unwrap();s}}// ---------- end scannner ----------use std::io::Write;fn main() {let sc = scanner::read_string();let mut sc = scanner::Scanner::new(&sc);let out = std::io::stdout();let mut out = std::io::BufWriter::new(out.lock());run(&mut sc, &mut out);}fn run(sc: &mut scanner::Scanner, out: &mut std::io::BufWriter<std::io::StdoutLock>) {let n: usize = sc.next();let m: usize = sc.next();let q: usize = sc.next();let mut c: Vec<_> = (0..m).map(|_| sc.next::<usize>() - 1).collect();let mut cent = CentroidDecomposition::new(n);for _ in 1..n {let a = sc.next::<usize>() - 1;let b = sc.next::<usize>() - 1;cent.add_edge(a, b);}cent.build();let cent = cent;let mut memo = vec![];for r in 0.. {let mut dp = vec![n as i64; n];let mut q = std::collections::VecDeque::new();for i in 0..n {if cent.rank(i) == r {dp[i] = 0;q.push_back(i);}}if q.is_empty() {break;}while let Some(v) = q.pop_front() {let d = dp[v] + 1;for &u in cent.graph[v].iter() {if cent.rank(u) >= r && dp[u] > d {dp[u] = d;q.push_back(u);}}}memo.push(dp);}// 距離の和、個数let mut all = vec![(0, 0); n];let mut sub = vec![(0, 0); n];for &c in c.iter() {let belong = cent.belong(c);for (dp, &g) in memo.iter().zip(belong.iter().rev()) {all[g].0 += dp[c];all[g].1 += 1;}for (dp, &g) in memo.iter().zip(belong.iter().rev().skip(1)) {sub[g].0 += dp[c];sub[g].1 += 1;}}for _ in 0..q {let op: u8 = sc.next();if op == 1 {let p = sc.next::<usize>() - 1;let d = sc.next::<usize>() - 1;for &(sign, v) in [(-1, c[p]), (1, d)].iter() {let belong = cent.belong(v);for (dp, &g) in memo.iter().zip(belong.iter().rev()) {all[g].0 += sign * dp[v];all[g].1 += sign;}for (dp, &g) in memo.iter().zip(belong.iter().rev().skip(1)) {sub[g].0 += sign * dp[v];sub[g].1 += sign;}}c[p] = d;} else {let e = sc.next::<usize>() - 1;let belong = cent.belong(e);let mut ans = 0;for (dp, &g) in memo.iter().zip(belong.iter().rev()) {ans += all[g].0;ans += all[g].1 * dp[e];}for (dp, &g) in memo.iter().zip(belong.iter().rev().skip(1)) {ans -= sub[g].0;ans -= sub[g].1 * dp[e];}writeln!(out, "{}", ans).ok();}}}