結果
問題 | No.2337 Equidistant |
ユーザー |
![]() |
提出日時 | 2023-06-02 22:01:17 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 312 ms / 4,000 ms |
コード長 | 9,063 bytes |
コンパイル時間 | 27,599 ms |
コンパイル使用メモリ | 377,528 KB |
実行使用メモリ | 38,516 KB |
最終ジャッジ日時 | 2024-12-28 17:56:24 |
合計ジャッジ時間 | 32,767 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 28 |
ソースコード
use std::io::Write;fn run() {input! {n: usize,q: usize,e: [(usize1, usize1); n - 1],ask: [(usize1, usize1); q],}let mut hld = HLD::new(n);for (a, b) in e {hld.add_edge(a, b);}hld.build(0);let out = std::io::stdout();let mut out = std::io::BufWriter::new(out.lock());let mut up = vec![];let mut down = vec![];let mut solve = |s: usize, t: usize| -> i32 {assert!(s != t);hld.path(s, t, &mut up, &mut down);let len = up.iter().chain(down.iter()).fold(0, |s, p| s + p.1 - p.0);if len % 2 == 0 {return 0;}let mid = hld.jump(s, t, len / 2, &mut up, &mut down).unwrap();let mut ans = n as i32;for &x in [s, t].iter() {let v = hld.next(mid, x);if hld.parent(v).map_or(false, |p| p == mid) {let p = hld.sub_tree(v);ans -= (p.1 - p.0) as i32;} else {let p = hld.sub_tree(mid);ans -= (n - (p.1 - p.0)) as i32;}}ans};for (s, t) in ask {let ans = solve(s, t);writeln!(out, "{}", ans).ok();}}fn main() {run();}// ---------- begin input macro ----------// reference: https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8#[macro_export]macro_rules! input {(source = $s:expr, $($r:tt)*) => {let mut iter = $s.split_whitespace();input_inner!{iter, $($r)*}};($($r:tt)*) => {let s = {use std::io::Read;let mut s = String::new();std::io::stdin().read_to_string(&mut s).unwrap();s};let mut iter = s.split_whitespace();input_inner!{iter, $($r)*}};}#[macro_export]macro_rules! input_inner {($iter:expr) => {};($iter:expr, ) => {};($iter:expr, $var:ident : $t:tt $($r:tt)*) => {let $var = read_value!($iter, $t);input_inner!{$iter $($r)*}};}#[macro_export]macro_rules! read_value {($iter:expr, ( $($t:tt),* )) => {( $(read_value!($iter, $t)),* )};($iter:expr, [ $t:tt ; $len:expr ]) => {(0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()};($iter:expr, chars) => {read_value!($iter, String).chars().collect::<Vec<char>>()};($iter:expr, bytes) => {read_value!($iter, String).bytes().collect::<Vec<u8>>()};($iter:expr, usize1) => {read_value!($iter, usize) - 1};($iter:expr, $t:ty) => {$iter.next().unwrap().parse::<$t>().expect("Parse error")};}// ---------- end input macro ----------// ---------- begin Heavy-Light decomposition ----------pub struct HLD {size: usize,edge: Vec<(usize, usize)>,child: Vec<Vec<usize>>,path_root: Vec<usize>,parent: Vec<usize>,left: Vec<usize>,right: Vec<usize>,inverse: Vec<usize>,}impl HLD {pub fn new(size: usize) -> Self {assert!(size <= 10usize.pow(8));HLD {size: size,edge: Vec::with_capacity(size - 1),child: Vec::new(),path_root: Vec::new(),parent: Vec::new(),left: Vec::new(),right: Vec::new(),inverse: Vec::new(),}}pub fn add_edge(&mut self, a: usize, b: usize) {assert!(a != b && a < self.size && b < self.size);self.edge.push((a, b));}pub fn build(&mut self, root: usize) {assert!(self.edge.len() + 1 == self.size);let size = self.size;let mut cnt = vec![0; size];for &(a, b) in self.edge.iter() {cnt[a] += 1;cnt[b] += 1;}let mut child = cnt.into_iter().map(|c| Vec::with_capacity(c)).collect::<Vec<_>>();for &(a, b) in self.edge.iter() {child[a].push(b);child[b].push(a);}let mut parent = vec![size; size];let mut q = Vec::with_capacity(size);q.push(root);parent[root] = root;for i in 0..size {let v = q[i];for u in child[v].clone() {assert!(parent[u] == size);parent[u] = v;child[u].retain(|e| *e != v);q.push(u);}}let mut sum = vec![1; size];for &v in q.iter().rev() {let child = &mut child[v];if !child.is_empty() {let (pos, _) = child.iter().enumerate().max_by_key(|p| sum[*p.1]).unwrap();child.swap(0, pos);sum[v] = 1 + child.iter().fold(0, |s, a| s + sum[*a]);}}let mut path_root = (0..size).collect::<Vec<_>>();let mut left = vec![0; size];let mut right = vec![0; size];let mut dfs = vec![(root, false)];let mut id = 0;while let Some((v, end)) = dfs.pop() {if end {right[v] = id;continue;}left[v] = id;id += 1;dfs.push((v, true));let child = &child[v];if !child.is_empty() {for &u in child[1..].iter() {path_root[u] = u;dfs.push((u, false));}let u = child[0];path_root[u] = path_root[v];dfs.push((u, false));}}let mut inverse = vec![size; size];for (i, l) in left.iter().enumerate() {inverse[*l] = i;}self.child = child;self.parent = parent;self.left = left;self.right = right;self.path_root = path_root;self.inverse = inverse;}pub fn lca(&self, mut a: usize, mut b: usize) -> usize {assert!(a < self.size && b < self.size);let path = &self.path_root;let parent = &self.parent;let index = &self.left;while path[a] != path[b] {if index[a] > index[b] {std::mem::swap(&mut a, &mut b);}b = parent[path[b]];}std::cmp::min((index[a], a), (index[b], b)).1}pub fn path(&self,src: usize,dst: usize,up: &mut Vec<(usize, usize)>,down: &mut Vec<(usize, usize)>,) {assert!(src < self.size && dst < self.size);up.clear();down.clear();let path = &self.path_root;let parent = &self.parent;let index = &self.left;let mut x = src;let mut y = dst;while path[x] != path[y] {if index[x] > index[y] {let p = path[x];assert!(p == path[p]);up.push((index[p], index[x] + 1));x = parent[p];} else {let p = path[y];assert!(p == path[p]);down.push((index[p], index[y] + 1));y = parent[p];}}if index[x] <= index[y] {down.push((index[x], index[y] + 1));} else {up.push((index[y], index[x] + 1));}down.reverse();}pub fn sub_tree(&self, v: usize) -> (usize, usize) {assert!(v < self.size);(self.left[v], self.right[v])}pub fn parent(&self, v: usize) -> Option<usize> {assert!(v < self.size);let p = self.parent[v];if p == v {None} else {Some(p)}}// s -> t へのパスの2番目の頂点を返すpub fn next(&self, s: usize, t: usize) -> usize {assert!(s < self.size && t < self.size && s != t);let (a, b) = self.sub_tree(s);let (c, d) = self.sub_tree(t);if !(a <= c && d <= b) {return self.parent[s];}let mut pos = t;let mut pre = t;while self.path_root[s] != self.path_root[pos] {pre = self.path_root[pos];pos = self.parent[pre];}if s == pos {pre} else {self.child[s][0]}}pub fn vertex(&self, x: usize) -> usize {assert!(x < self.size);self.inverse[x]}pub fn jump(&self, s: usize, t: usize, mut k: usize, up: &mut Vec<(usize, usize)>, down: &mut Vec<(usize, usize)>) -> Option<usize> {assert!(s.max(t) < self.size);self.path(s, t, up, down);for (l, r) in up.drain(..) {if k < r - l {return Some(self.vertex(r - 1 - k));}k -= r - l;}for (l, r) in down.drain(..) {if k < r - l {return Some(self.vertex(l + k));}k -= r - l;}None}}// ---------- end Heavy-Light decomposition ----------