結果

問題 No.2337 Equidistant
ユーザー akakimidori
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

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

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 ----------
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0