結果
| 問題 | No.3442 Good Vertex Connectivity |
| コンテスト | |
| ユーザー |
👑  ArcAki
|
| 提出日時 | 2026-02-17 01:44:56 |
| 言語 | Rust (1.93.0 + proconio + num + itertools) |
| 結果 |
AC
|
| 実行時間 | 1,265 ms / 3,000 ms |
| コード長 | 8,580 bytes |
| 記録 | |
| コンパイル時間 | 13,984 ms |
| コンパイル使用メモリ | 216,868 KB |
| 実行使用メモリ | 329,004 KB |
| 最終ジャッジ日時 | 2026-02-17 01:46:17 |
| 合計ジャッジ時間 | 71,831 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 69 |
コンパイルメッセージ
warning: unused variable: `idx`
--> src/main.rs:120:31
|
120 | while let Some((v, p, idx, entered)) = st.pop() {
| ^^^ help: if this is intentional, prefix it with an underscore: `_idx`
|
= note: `#[warn(unused_variables)]` (part of `#[warn(unused)]`) on by default
warning: variable does not need to be mutable
--> src/main.rs:169:23
|
169 | pub fn lca(&self, mut u: usize, mut v: usize) -> usize {
| ----^
| |
| help: remove this `mut`
|
= note: `#[warn(unused_mut)]` (part of `#[warn(unused)]`) on by default
warning: variable does not need to be mutable
--> src/main.rs:169:37
|
169 | pub fn lca(&self, mut u: usize, mut v: usize) -> usize {
| ----^
| |
| help: remove this `mut`
warning: variable does not need to be mutable
--> src/main.rs:190:39
|
190 | pub fn climb(&self, mut v: usize, mut k: usize) -> usize {
| ----^
| |
| help: remove this `mut`
warning: field `n` is never read
--> src/main.rs:94:5
|
93 | pub struct STLCA {
| ----- field in this struct
94 | n: usize,
| ^
|
= note: `STLCA` has derived impls for the traits `Debug` and `Clone`, but these are intentionally ignored during dead code analysis
= note: `#[warn(dead_code)]` (part of `#[warn(unused)]`) on by default
ソースコード
#[allow(unused_imports)]
use std::{
cmp::{self, Reverse, Ordering},
collections::*,
io::{self, Read},
mem::swap,
};
#[allow(unused)]
use proconio::{input, marker::*};
pub trait SegtreeMonoid {
type S: Clone;
fn identity(&self) -> Self::S;
fn op(&self, a: &Self::S, b: &Self::S) -> Self::S;
}
pub struct Segtree<M: SegtreeMonoid> {
n: usize,
data: Vec<M::S>,
m: M,
}
impl<M: SegtreeMonoid> Segtree<M> {
pub fn new(n: usize, m: M) -> Self {
let n = n.next_power_of_two();
let e = m.identity();
let data = vec![e; 2 * n];
Segtree { n, data, m }
}
pub fn set(&mut self, i: usize, x: M::S) {
let mut p = i + self.n;
self.data[p] = x;
while p > 1 {
p >>= 1;
self.data[p] = self.m.op(&self.data[p << 1], &self.data[(p << 1) | 1]);
}
}
pub fn prod(&self, l: usize, r: usize) -> M::S {
let mut p_l = l + self.n;
let mut p_r = r + self.n;
let mut res_l = self.m.identity();
let mut res_r = self.m.identity();
while p_l < p_r {
if p_l & 1 == 1 {
res_l = self.m.op(&res_l, &self.data[p_l]);
p_l += 1;
}
if p_r & 1 == 1 {
p_r -= 1;
res_r = self.m.op(&self.data[p_r], &res_r);
}
p_l >>= 1;
p_r >>= 1;
}
self.m.op(&res_l, &res_r)
}
}
/* ===== Sparse Table for RMQ (min) ===== */
#[derive(Clone, Debug)]
pub struct SparseTableMI<T: Ord + Copy> {
table: Vec<Vec<T>>,
}
impl<T: Ord + Copy> SparseTableMI<T> {
pub fn build(a: &Vec<T>) -> Self {
let n = a.len();
let mut table: Vec<Vec<T>> = Vec::new();
table.push(a.clone());
let mut k = 1;
while (1usize << k) <= n {
let prev = &table[k - 1];
let len = n - (1usize << k) + 1;
let mut cur = Vec::with_capacity(len);
let w = 1usize << (k - 1);
for i in 0..len {
cur.push(prev[i].min(prev[i + w]));
}
table.push(cur);
k += 1;
}
Self { table }
}
pub fn query(&self, l: usize, r: usize) -> T {
let s = r - l;
let k = (usize::BITS - 1 - s.leading_zeros()) as usize;
let w = 1usize << k;
self.table[k][l].min(self.table[k][r - w])
}
}
/* ===== LCA + depth + tin/tout + binary lifting ===== */
#[derive(Clone, Debug)]
pub struct STLCA {
n: usize,
first: Vec<usize>,
rmq: SparseTableMI<(usize, usize)>,
depth: Vec<usize>,
up: Vec<Vec<usize>>,
tin: Vec<usize>,
tout: Vec<usize>,
}
impl STLCA {
pub fn new(n: usize, root: usize, g: &Vec<Vec<usize>>) -> Self {
let lg = 20; // enough for n<=2e5
let mut depth = vec![0usize; n];
let mut parent = vec![root; n];
let mut tin = vec![0usize; n];
let mut tout = vec![0usize; n];
let mut timer = 0usize;
// iterative DFS: also build Euler tour for LCA RMQ
let mut first = vec![0usize; n];
let mut euler: Vec<(usize, usize)> = Vec::with_capacity(2 * n);
// stack: (v, p, next_child_index, entered?)
let mut st: Vec<(usize, usize, usize, bool)> = Vec::new();
st.push((root, root, 0, false));
while let Some((v, p, idx, entered)) = st.pop() {
if !entered {
parent[v] = p;
tin[v] = timer;
timer += 1;
first[v] = euler.len();
euler.push((depth[v], v));
st.push((v, p, 0, true));
for &to in g[v].iter().rev() {
if to == p {
continue;
}
depth[to] = depth[v] + 1;
st.push((to, v, 0, false));
}
} else {
// leaving v: push parent into euler (if exists)
tout[v] = timer;
if v != root {
euler.push((depth[p], p));
}
}
}
// Build binary lifting
let mut up = vec![vec![root; n]; lg];
up[0] = parent.clone();
for k in 1..lg {
for v in 0..n {
up[k][v] = up[k - 1][up[k - 1][v]];
}
}
let rmq = SparseTableMI::build(&euler);
STLCA {
n,
first,
rmq,
depth,
up,
tin,
tout,
}
}
#[inline(always)]
pub fn lca(&self, mut u: usize, mut v: usize) -> usize {
let mut fu = self.first[u];
let mut fv = self.first[v];
if fu > fv {
swap(&mut fu, &mut fv);
}
self.rmq.query(fu, fv + 1).1
}
#[inline(always)]
pub fn dist(&self, u: usize, v: usize) -> u64 {
let p = self.lca(u, v);
(self.depth[u] + self.depth[v] - 2 * self.depth[p]) as u64
}
#[inline(always)]
pub fn is_ancestor(&self, a: usize, b: usize) -> bool {
self.tin[a] <= self.tin[b] && self.tout[b] <= self.tout[a]
}
#[inline(always)]
pub fn climb(&self, mut v: usize, mut k: usize) -> usize {
let lg = self.up.len();
for i in 0..lg {
if (k >> i) & 1 == 1 {
v = self.up[i][v];
}
}
v
}
// a is ancestor of b, a != b: return the child of a on path to b
#[inline(always)]
pub fn child_on_path(&self, a: usize, b: usize) -> usize {
// lift b up to depth[a]+1
let da = self.depth[a];
let db = self.depth[b];
let k = db - da - 1;
self.climb(b, k)
}
}
/* ===== segment monoid for "virtual tree perimeter" ===== */
struct M {
lca: STLCA,
}
impl SegtreeMonoid for M {
// (first, last, sum_dist_consecutive)
type S = (usize, usize, u64);
fn identity(&self) -> Self::S {
(!0, !0, 0)
}
fn op(&self, a: &Self::S, b: &Self::S) -> Self::S {
let first = if a.0 == !0 { b.0 } else { a.0 };
let last = if b.1 == !0 { a.1 } else { b.1 };
let mut sum = a.2 + b.2;
if a.1 != !0 && b.0 != !0 {
sum += self.lca.dist(a.1, b.0);
}
(first, last, sum)
}
}
#[inline(always)]
fn steiner_vertex_count(lca: &STLCA, s: (usize, usize, u64)) -> u64 {
if s.0 == !0 {
return 0;
}
// edges = (sum_consecutive + dist(last, first)) / 2
let edges = (s.2 + lca.dist(s.0, s.1)) / 2;
edges + 1
}
const MULTI: bool = false;
fn solve() {
input! {
n: usize,
e: [(Usize1, Usize1); n-1],
mut c: [u8; n],
q: usize,
}
let mut g = vec![Vec::<usize>::new(); n];
for &(u, v) in &e {
g[u].push(v);
g[v].push(u);
}
let lca = STLCA::new(n, 0, &g);
let m = M { lca: lca.clone() };
let mut seg = Segtree::new(n, m);
// build initial black set on tin-order
for v in 0..n {
if c[v] == 1 {
seg.set(lca.tin[v], (v, v, 0));
}
}
for _ in 0..q {
input! { t: u8 }
if t == 1 {
input! { v: Usize1 }
if c[v] == 0 {
c[v] = 1;
seg.set(lca.tin[v], (v, v, 0));
} else {
c[v] = 0;
seg.set(lca.tin[v], (!0, !0, 0));
}
} else {
input! { x: Usize1, y: Usize1 }
if x == y {
// y is on path(v,x) for all v
let all = seg.prod(0, n);
println!("{}", steiner_vertex_count(&lca, all));
continue;
}
let p = lca.lca(x, y);
if p != y {
// good vertices are inside subtree(y)
let s = seg.prod(lca.tin[y], lca.tout[y]);
println!("{}", steiner_vertex_count(&lca, s));
} else {
// y is ancestor of x: exclude subtree(child_on_path(y,x))
let child = lca.child_on_path(y, x);
let a = seg.prod(0, lca.tin[child]);
let b = seg.prod(lca.tout[child], n);
// combine as one set (already in tin-order: [0,tin) then [tout,n))
let s = seg.m.op(&a, &b);
println!("{}", steiner_vertex_count(&lca, s));
}
}
}
}
fn main() {
if MULTI {
input! { t: usize }
for _ in 0..t {
solve();
}
} else {
solve();
}
}