#977374 (Rust) No.399 動的な領主

提出ソース
結果

問題	No.399 動的な領主
ユーザー	あさくち
提出日時	2024-04-25 19:34:37
言語	Rust (1.77.0)
結果	AC
実行時間	584 ms / 2,000 ms
コード長	18,805 bytes
コンパイル時間	3,096 ms
コンパイル使用メモリ	192,728 KB
実行使用メモリ	47,964 KB
最終ジャッジ日時	2024-04-25 19:34:50
合計ジャッジ時間	9,846 ms
ジャッジサーバーID （参考情報）	judge5 / judge2
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 6,816 KB
testcase_01	AC	0 ms 6,816 KB
testcase_02	AC	1 ms 6,816 KB
testcase_03	AC	1 ms 6,944 KB
testcase_04	AC	2 ms 6,940 KB
testcase_05	AC	29 ms 6,940 KB
testcase_06	AC	464 ms 29,488 KB
testcase_07	AC	537 ms 29,460 KB
testcase_08	AC	543 ms 28,980 KB
testcase_09	AC	562 ms 28,976 KB
testcase_10	AC	3 ms 6,940 KB
testcase_11	AC	25 ms 6,940 KB
testcase_12	AC	402 ms 28,480 KB
testcase_13	AC	382 ms 28,608 KB
testcase_14	AC	92 ms 47,940 KB
testcase_15	AC	134 ms 47,964 KB
testcase_16	AC	212 ms 37,324 KB
testcase_17	AC	584 ms 29,052 KB
testcase_18	AC	578 ms 29,032 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
pub use __cargo_equip::prelude::*;

use acl_lazysegtree::{LazySegtree, MapMonoid};
use acl_segtree::Monoid;
use hld::Hld;
use proconio::{input, marker::Usize1};

#[derive(Clone)]
struct Data {
    value: usize,
    size: usize,
}

struct Sum;

impl Monoid for Sum {
    ///
    /// モノイドの型
    ///
    type S = Data;

    ///
    /// 単位元
    ///
    fn identity() -> Self::S {
        Data { value: 0, size: 0 }
    }

    ///
    /// 二項演算
    ///
    fn binary_operation(a: &Self::S, b: &Self::S) -> Self::S {
        Data {
            value: a.value + b.value,
            size: a.size + b.size,
        }
    }
}

struct SumAdd;

impl MapMonoid for SumAdd {
    type M = Sum;
    /// 写像の型
    type F = usize;

    ///
    /// 恒等写像
    /// 全ての`a`に対して`mapping(id, a) = a`となるもの
    ///
    fn identity_map() -> Self::F {
        0
    }

    ///
    /// f(x) を返す関数
    ///
    /// dataの値`x`に対して作用させる関数
    ///
    fn mapping(f: &Self::F, x: &<Self::M as Monoid>::S) -> <Self::M as Monoid>::S {
        Data {
            value: x.value + x.size * f,
            size: x.size,
        }
    }

    ///
    /// f∘g を返す関数
    ///
    /// `g` がこれまでの操作、`f` が後に追加する操作で、
    ///「その2つの操作を順に行うようなひとまとめの操作（合成写像）」を返す
    ///
    fn composition(&f: &Self::F, &g: &Self::F) -> Self::F {
        f + g
    }
}

fn main() {
    input! {
        n: usize,
        u_v: [(Usize1, Usize1); n - 1],
        q: usize,
        a_b: [(Usize1, Usize1); q],
    }

    let mut list = vec![Vec::new(); n];

    for &(u, v) in &u_v {
        list[u].push(v);
        list[v].push(u);
    }

    let hld = Hld::new(0, &list);

    // println!("{:?}", hld);

    let mut tree = LazySegtree::<SumAdd>::from(vec![Data { value: 0, size: 1 }; n]);

    let mut result = 0;

    for &(a, b) in &a_b {
        // println!("---- {} {}", a, b);

        for (u, v) in hld.iter_v(a, b) {
            // println!("{}({}) {}({})", hld.ord()[u], u, hld.ord()[v], v);

            tree.apply_range(u, v + 1, 1);

            result += tree.prod(u, v + 1).value;
        }

        // for i in 0..n {
        //     println!("i {} w {}", i, tree.get(i).value);
        // }
    }

    println!("{}", result);
}

// The following code was expanded by `cargo-equip`.

///  # Bundled libraries
/// 
///  - `ac-library-rs-parted-internal-bit 0.1.0 (git+https://github.com/qryxip/ac-library-rs-parted#77261929d6551609cf352f4f9e05b34bafd5a8f7)`              licensed under `CC0-1.0`   as `crate::__cargo_equip::crates::__ac_library_rs_parted_internal_bit_0_1_0`
///  - `ac-library-rs-parted-internal-type-traits 0.1.0 (git+https://github.com/qryxip/ac-library-rs-parted#77261929d6551609cf352f4f9e05b34bafd5a8f7)`      licensed under `CC0-1.0`   as `crate::__cargo_equip::crates::__ac_library_rs_parted_internal_type_traits_0_1_0`
///  - `ac-library-rs-parted-lazysegtree 0.1.0 (git+https://github.com/qryxip/ac-library-rs-parted#77261929d6551609cf352f4f9e05b34bafd5a8f7)`               licensed under `CC0-1.0`   as `crate::__cargo_equip::crates::acl_lazysegtree`
///  - `ac-library-rs-parted-segtree 0.1.0 (git+https://github.com/qryxip/ac-library-rs-parted#77261929d6551609cf352f4f9e05b34bafd5a8f7)`                   licensed under `CC0-1.0`   as `crate::__cargo_equip::crates::acl_segtree`
///  - `hld 0.1.0 (git+https://github.com/ngtkana/ac-adapter-rs.git?rev=624ecef1fb67c2e0a42752fb9cd5339f99e5c318#624ecef1fb67c2e0a42752fb9cd5339f99e5c318)` licensed under **missing** as `crate::__cargo_equip::crates::hld`
#[cfg_attr(any(), rustfmt::skip)]
#[allow(unused)]
mod __cargo_equip {
    pub(crate) mod crates {
        pub mod __ac_library_rs_parted_internal_bit_0_1_0 {pub use self::internal_bit::*;mod internal_bit{#[allow(dead_code)]pub fn ceil_pow2(n:u32)->u32{32-n.saturating_sub(1).leading_zeros()}}}
        pub mod __ac_library_rs_parted_internal_type_traits_0_1_0 {pub use self::internal_type_traits::*;mod internal_type_traits{use std::{fmt,iter::{Product,Sum},ops::{Add,AddAssign,BitAnd,BitAndAssign,BitOr,BitOrAssign,BitXor,BitXorAssign,Div,DivAssign,Mul,MulAssign,Not,Rem,RemAssign,Shl,ShlAssign,Shr,ShrAssign,Sub,SubAssign,},};pub trait Integral:'static+Send+Sync+Copy+Ord+Not<Output=Self>+Add<Output=Self>+Sub<Output=Self>+Mul<Output=Self>+Div<Output=Self>+Rem<Output=Self>+AddAssign+SubAssign+MulAssign+DivAssign+RemAssign+Sum+Product+BitOr<Output=Self>+BitAnd<Output=Self>+BitXor<Output=Self>+BitOrAssign+BitAndAssign+BitXorAssign+Shl<Output=Self>+Shr<Output=Self>+ShlAssign+ShrAssign+fmt::Display+fmt::Debug+fmt::Binary+fmt::Octal+Zero+One+BoundedBelow+BoundedAbove{}pub trait Zero{fn zero()->Self;}pub trait One{fn one()->Self;}pub trait BoundedBelow{fn min_value()->Self;}pub trait BoundedAbove{fn max_value()->Self;}macro_rules!impl_integral{($($ty:ty),*)=>{$(impl Zero for$ty{#[inline]fn zero()->Self{0}}impl One for$ty{#[inline]fn one()->Self{1}}impl BoundedBelow for$ty{#[inline]fn min_value()->Self{Self::min_value()}}impl BoundedAbove for$ty{#[inline]fn max_value()->Self{Self::max_value()}}impl Integral for$ty{})*};}impl_integral!(i8,i16,i32,i64,i128,isize,u8,u16,u32,u64,u128,usize);}}
        pub mod acl_lazysegtree {use crate::__cargo_equip::preludes::acl_lazysegtree::*;use crate::__cargo_equip::crates::__ac_library_rs_parted_internal_bit_0_1_0 as internal_bit;use crate::__cargo_equip::crates::acl_segtree as segtree;pub use self::lazysegtree::*;mod lazysegtree{use crate::__cargo_equip::preludes::acl_lazysegtree::*;use super::internal_bit::ceil_pow2;use super::segtree::Monoid;pub trait MapMonoid{type M:Monoid;type F:Clone;fn identity_element()-><Self::M as Monoid>::S{Self::M::identity()}fn binary_operation(a:&<Self::M as Monoid>::S,b:&<Self::M as Monoid>::S,)-><Self::M as Monoid>::S{Self::M::binary_operation(a,b)}fn identity_map()->Self::F;fn mapping(f:&Self::F,x:&<Self::M as Monoid>::S)-><Self::M as Monoid>::S;fn composition(f:&Self::F,g:&Self::F)->Self::F;}impl<F:MapMonoid>Default for LazySegtree<F>{fn default()->Self{Self::new(0)}}impl<F:MapMonoid>LazySegtree<F>{pub fn new(n:usize)->Self{vec![F::identity_element();n].into()}}impl<F:MapMonoid>From<Vec<<F::M as Monoid>::S>>for LazySegtree<F>{fn from(v:Vec<<F::M as Monoid>::S>)->Self{let n=v.len();let log=ceil_pow2(n as u32)as usize;let size=1<<log;let mut d=vec![F::identity_element();2*size];let lz=vec![F::identity_map();size];d[size..(size+n)].clone_from_slice(&v);let mut ret=LazySegtree{n,size,log,d,lz,};for i in(1..size).rev(){ret.update(i);}ret}}impl<F:MapMonoid>LazySegtree<F>{pub fn set(&mut self,mut p:usize,x:<F::M as Monoid>::S){assert!(p<self.n);p+=self.size;for i in(1..=self.log).rev(){self.push(p>>i);}self.d[p]=x;for i in 1..=self.log{self.update(p>>i);}}pub fn get(&mut self,mut p:usize)-><F::M as Monoid>::S{assert!(p<self.n);p+=self.size;for i in(1..=self.log).rev(){self.push(p>>i);}self.d[p].clone()}pub fn prod(&mut self,mut l:usize,mut r:usize)-><F::M as Monoid>::S{assert!(l<=r&&r<=self.n);if l==r{return F::identity_element();}l+=self.size;r+=self.size;for i in(1..=self.log).rev(){if((l>>i)<<i)!=l{self.push(l>>i);}if((r>>i)<<i)!=r{self.push(r>>i);}}let mut sml=F::identity_element();let mut smr=F::identity_element();while l<r{if l&1!=0{sml=F::binary_operation(&sml,&self.d[l]);l+=1;}if r&1!=0{r-=1;smr=F::binary_operation(&self.d[r],&smr);}l>>=1;r>>=1;}F::binary_operation(&sml,&smr)}pub fn all_prod(&self)-><F::M as Monoid>::S{self.d[1].clone()}pub fn apply(&mut self,mut p:usize,f:F::F){assert!(p<self.n);p+=self.size;for i in(1..=self.log).rev(){self.push(p>>i);}self.d[p]=F::mapping(&f,&self.d[p]);for i in 1..=self.log{self.update(p>>i);}}pub fn apply_range(&mut self,mut l:usize,mut r:usize,f:F::F){assert!(l<=r&&r<=self.n);if l==r{return;}l+=self.size;r+=self.size;for i in(1..=self.log).rev(){if((l>>i)<<i)!=l{self.push(l>>i);}if((r>>i)<<i)!=r{self.push((r-1)>>i);}}{let l2=l;let r2=r;while l<r{if l&1!=0{self.all_apply(l,f.clone());l+=1;}if r&1!=0{r-=1;self.all_apply(r,f.clone());}l>>=1;r>>=1;}l=l2;r=r2;}for i in 1..=self.log{if((l>>i)<<i)!=l{self.update(l>>i);}if((r>>i)<<i)!=r{self.update((r-1)>>i);}}}pub fn max_right<G>(&mut self,mut l:usize,g:G)->usize where G:Fn(<F::M as Monoid>::S)->bool,{assert!(l<=self.n);assert!(g(F::identity_element()));if l==self.n{return self.n;}l+=self.size;for i in(1..=self.log).rev(){self.push(l>>i);}let mut sm=F::identity_element();while{while l%2==0{l>>=1;}if!g(F::binary_operation(&sm,&self.d[l])){while l<self.size{self.push(l);l*=2;let res=F::binary_operation(&sm,&self.d[l]);if g(res.clone()){sm=res;l+=1;}}return l-self.size;}sm=F::binary_operation(&sm,&self.d[l]);l+=1;{let l=l as isize;(l&-l)!=l}}{}self.n}pub fn min_left<G>(&mut self,mut r:usize,g:G)->usize where G:Fn(<F::M as Monoid>::S)->bool,{assert!(r<=self.n);assert!(g(F::identity_element()));if r==0{return 0;}r+=self.size;for i in(1..=self.log).rev(){self.push((r-1)>>i);}let mut sm=F::identity_element();while{r-=1;while r>1&&r%2!=0{r>>=1;}if!g(F::binary_operation(&self.d[r],&sm)){while r<self.size{self.push(r);r=2*r+1;let res=F::binary_operation(&self.d[r],&sm);if g(res.clone()){sm=res;r-=1;}}return r+1-self.size;}sm=F::binary_operation(&self.d[r],&sm);{let r=r as isize;(r&-r)!=r}}{}0}}pub struct LazySegtree<F>where F:MapMonoid,{n:usize,size:usize,log:usize,d:Vec<<F::M as Monoid>::S>,lz:Vec<F::F>,}impl<F>LazySegtree<F>where F:MapMonoid,{fn update(&mut self,k:usize){self.d[k]=F::binary_operation(&self.d[2*k],&self.d[2*k+1]);}fn all_apply(&mut self,k:usize,f:F::F){self.d[k]=F::mapping(&f,&self.d[k]);if k<self.size{self.lz[k]=F::composition(&f,&self.lz[k]);}}fn push(&mut self,k:usize){self.all_apply(2*k,self.lz[k].clone());self.all_apply(2*k+1,self.lz[k].clone());self.lz[k]=F::identity_map();}}use std::fmt::{Debug,Error,Formatter,Write};impl<F>Debug for LazySegtree<F>where F:MapMonoid,F::F:Debug,<F::M as Monoid>::S:Debug,{fn fmt(&self,f:&mut Formatter<'_>)->Result<(),Error>{for i in 0..self.log{for j in 0..1<<i{f.write_fmt(format_args!("{:?}[{:?}]\t",self.d[(1<<i)+j],self.lz[(1<<i)+j]))?;}f.write_char('\n')?;}for i in 0..self.size{f.write_fmt(format_args!("{:?}\t",self.d[self.size+i]))?;}Ok(())}}}}
        pub mod acl_segtree {use crate::__cargo_equip::preludes::acl_segtree::*;use crate::__cargo_equip::crates::__ac_library_rs_parted_internal_bit_0_1_0 as internal_bit;use crate::__cargo_equip::crates::__ac_library_rs_parted_internal_type_traits_0_1_0 as internal_type_traits;pub use self::segtree::*;mod segtree{use crate::__cargo_equip::preludes::acl_segtree::*;use super::internal_bit::ceil_pow2;use super::internal_type_traits::{BoundedAbove,BoundedBelow,One,Zero};use std::cmp::{max,min};use std::convert::Infallible;use std::marker::PhantomData;use std::ops::{Add,Mul};pub trait Monoid{type S:Clone;fn identity()->Self::S;fn binary_operation(a:&Self::S,b:&Self::S)->Self::S;}pub struct Max<S>(Infallible,PhantomData<fn()->S>);impl<S>Monoid for Max<S>where S:Copy+Ord+BoundedBelow,{type S=S;fn identity()->Self::S{S::min_value()}fn binary_operation(a:&Self::S,b:&Self::S)->Self::S{max(*a,*b)}}pub struct Min<S>(Infallible,PhantomData<fn()->S>);impl<S>Monoid for Min<S>where S:Copy+Ord+BoundedAbove,{type S=S;fn identity()->Self::S{S::max_value()}fn binary_operation(a:&Self::S,b:&Self::S)->Self::S{min(*a,*b)}}pub struct Additive<S>(Infallible,PhantomData<fn()->S>);impl<S>Monoid for Additive<S>where S:Copy+Add<Output=S>+Zero,{type S=S;fn identity()->Self::S{S::zero()}fn binary_operation(a:&Self::S,b:&Self::S)->Self::S{*a+*b}}pub struct Multiplicative<S>(Infallible,PhantomData<fn()->S>);impl<S>Monoid for Multiplicative<S>where S:Copy+Mul<Output=S>+One,{type S=S;fn identity()->Self::S{S::one()}fn binary_operation(a:&Self::S,b:&Self::S)->Self::S{*a**b}}impl<M:Monoid>Default for Segtree<M>{fn default()->Self{Segtree::new(0)}}impl<M:Monoid>Segtree<M>{pub fn new(n:usize)->Segtree<M>{vec![M::identity();n].into()}}impl<M:Monoid>From<Vec<M::S>>for Segtree<M>{fn from(v:Vec<M::S>)->Self{let n=v.len();let log=ceil_pow2(n as u32)as usize;let size=1<<log;let mut d=vec![M::identity();2*size];d[size..(size+n)].clone_from_slice(&v);let mut ret=Segtree{n,size,log,d};for i in(1..size).rev(){ret.update(i);}ret}}impl<M:Monoid>Segtree<M>{pub fn set(&mut self,mut p:usize,x:M::S){assert!(p<self.n);p+=self.size;self.d[p]=x;for i in 1..=self.log{self.update(p>>i);}}pub fn get(&self,p:usize)->M::S{assert!(p<self.n);self.d[p+self.size].clone()}pub fn prod(&self,mut l:usize,mut r:usize)->M::S{assert!(l<=r&&r<=self.n);let mut sml=M::identity();let mut smr=M::identity();l+=self.size;r+=self.size;while l<r{if l&1!=0{sml=M::binary_operation(&sml,&self.d[l]);l+=1;}if r&1!=0{r-=1;smr=M::binary_operation(&self.d[r],&smr);}l>>=1;r>>=1;}M::binary_operation(&sml,&smr)}pub fn all_prod(&self)->M::S{self.d[1].clone()}pub fn max_right<F>(&self,mut l:usize,f:F)->usize where F:Fn(&M::S)->bool,{assert!(l<=self.n);assert!(f(&M::identity()));if l==self.n{return self.n;}l+=self.size;let mut sm=M::identity();while{while l%2==0{l>>=1;}if!f(&M::binary_operation(&sm,&self.d[l])){while l<self.size{l*=2;let res=M::binary_operation(&sm,&self.d[l]);if f(&res){sm=res;l+=1;}}return l-self.size;}sm=M::binary_operation(&sm,&self.d[l]);l+=1;{let l=l as isize;(l&-l)!=l}}{}self.n}pub fn min_left<F>(&self,mut r:usize,f:F)->usize where F:Fn(&M::S)->bool,{assert!(r<=self.n);assert!(f(&M::identity()));if r==0{return 0;}r+=self.size;let mut sm=M::identity();while{r-=1;while r>1&&r%2==1{r>>=1;}if!f(&M::binary_operation(&self.d[r],&sm)){while r<self.size{r=2*r+1;let res=M::binary_operation(&self.d[r],&sm);if f(&res){sm=res;r-=1;}}return r+1-self.size;}sm=M::binary_operation(&self.d[r],&sm);{let r=r as isize;(r&-r)!=r}}{}0}fn update(&mut self,k:usize){self.d[k]=M::binary_operation(&self.d[2*k],&self.d[2*k+1]);}}pub struct Segtree<M>where M:Monoid,{n:usize,size:usize,log:usize,d:Vec<M::S>,}}}
        pub mod hld {use std::mem::swap;use std::usize::MAX;#[derive(Clone,Debug,Default,Hash,PartialEq,Eq)]pub struct Hld{child:Vec<Vec<usize>>,size:Vec<usize>,time:Vec<usize>,ord:Vec<usize>,parent:Vec<usize>,head:Vec<usize>,}impl Hld{pub fn new(root:usize,g:&[Vec<usize>])->Self{let(child,[size,time,ord,parent,head])=hld(root,g);Self{child,size,time,ord,parent,head,}}pub fn child(&self)->&[Vec<usize>]{&self.child}pub fn size(&self)->&[usize]{&self.size}pub fn time(&self)->&[usize]{&self.time}pub fn ord(&self)->&[usize]{&self.ord}pub fn parent(&self)->&[usize]{&self.parent}pub fn head(&self)->&[usize]{&self.head}pub fn is_adjacent(&self,u:usize,v:usize)->bool{assert!(u<self.child.len(),"範囲外です。");assert!(v<self.child.len(),"範囲外です。");self.parent[u]==v||u==self.parent[v]}pub fn adjacent_toward(&self,x:usize,toward:usize)->usize{assert!(x<self.child.len(),"範囲外です。");assert!(toward<self.child.len(),"範囲外です。");assert_ne!(x,toward,"`x = toward = {} となっており、方向がわかりません。",x);if self.is_ancestor_of(x,toward){self.child[x].iter().copied().find(|&y|self.is_ancestor_of(y,toward)).unwrap()}else{self.parent[x]}}pub fn dist(&self,u:usize,v:usize)->usize{self.iter_e(u,v).map(|(l,r)|r-l+1).sum::<usize>()}pub fn lca(&self,u:usize,v:usize)->usize{let(u,v)=self.iter_v(u,v).last().unwrap();self.ord[u.min(v)]}pub fn is_ancestor_of(&self,p:usize,u:usize)->bool{self.lca(p,u)==p}pub fn between(&self,a:usize,b:usize,c:usize)->bool{let mid=self.time[b];self.iter_v(a,c).any(|(left,right)|(left..=right).contains(&mid))}pub fn iter_v(&self,u:usize,v:usize)->IterV<'_>{IterV{hld:self,u,v,finish:false,}}pub fn iter_e(&self,u:usize,v:usize)->IterE<'_>{IterE{hld:self,u,v,finish:false,}}}#[derive(Clone,Debug,Hash,PartialEq,Eq)]pub struct IterV<'a>{hld:&'a Hld,u:usize,v:usize,finish:bool,}impl Iterator for IterV<'_>{type Item=(usize,usize);fn next(&mut self)->Option<Self::Item>{if self.finish{return None;}let Self{hld,u,v,..}=self;if hld.time[*u]>hld.time[*v]{swap(u,v);}Some(if hld.head[*u]==hld.head[*v]{self.finish=true;(hld.time[*u],hld.time[*v])}else{let h=hld.head[*v];let ans=(hld.time[h],hld.time[*v]);assert_ne!(hld.parent[h],h,"入力のグラフが非連結です。");*v=hld.parent[h];ans})}}#[derive(Clone,Debug,Hash,PartialEq,Eq)]pub struct IterE<'a>{hld:&'a Hld,u:usize,v:usize,finish:bool,}impl Iterator for IterE<'_>{type Item=(usize,usize);fn next(&mut self)->Option<Self::Item>{if self.finish{return None;}let Self{hld,u,v,..}=self;if hld.time[*u]>hld.time[*v]{swap(u,v);}if hld.head[*u]==hld.head[*v]{self.finish=true;if*u==*v{None}else{Some((hld.time[*u]+1,hld.time[*v]))}}else{let h=hld.head[*v];let ans=(hld.time[h],hld.time[*v]);assert_ne!(hld.parent[h],h,"入力のグラフが非連結です。");*v=hld.parent[h];Some(ans)}}}fn hld(root:usize,g:&[Vec<usize>])->(Vec<Vec<usize>>,[Vec<usize>;5]){let n=g.len();let mut size=vec![1;n];let mut child=vec![Vec::<usize>::new();n];dfs(root,root,g,&mut size,&mut child);let mut ord=Vec::new();let mut time=vec![MAX;n];let mut parent=vec![MAX;n];let mut head=vec![MAX;n];parent[root]=root;head[root]=root;efs(root,&child,&mut time,&mut ord,&mut parent,&mut head);assert!(parent.iter().all(|&x|x!=MAX),"入力が非連結です。");(child,[size,time,ord,parent,head])}fn dfs(x:usize,p:usize,g:&[Vec<usize>],size:&mut[usize],child:&mut[Vec<usize>]){let mut gx=g[x].iter().copied().filter(|&y|y!=p).collect::<Vec<_>>();if!gx.is_empty(){for&y in&gx{dfs(y,x,g,size,child);size[x]+=size[y];}let max_position=(0..gx.len()).max_by_key(|&i|size[gx[i]]).unwrap();gx.swap(0,max_position);}child[x]=gx;}fn efs(x:usize,g:&[Vec<usize>],time:&mut[usize],ord:&mut Vec<usize>,parent:&mut[usize],head:&mut[usize],){time[x]=ord.len();ord.push(x);if!g[x].is_empty(){let h=g[x][0];head[h]=head[x];parent[h]=x;efs(h,g,time,ord,parent,head);for&y in&g[x][1..]{head[y]=y;parent[y]=x;efs(y,g,time,ord,parent,head);}}}}
    }

    pub(crate) mod macros {
        pub mod __ac_library_rs_parted_internal_bit_0_1_0 {}
        pub mod __ac_library_rs_parted_internal_type_traits_0_1_0 {}
        pub mod acl_lazysegtree {}
        pub mod acl_segtree {}
        pub mod hld {}
    }

    pub(crate) mod prelude {pub use crate::__cargo_equip::crates::*;}

    mod preludes {
        pub mod __ac_library_rs_parted_internal_bit_0_1_0 {}
        pub mod __ac_library_rs_parted_internal_type_traits_0_1_0 {}
        pub mod acl_lazysegtree {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::{__ac_library_rs_parted_internal_bit_0_1_0 as __acl_internal_bit,acl_segtree as __acl_segtree};}
        pub mod acl_segtree {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::{__ac_library_rs_parted_internal_bit_0_1_0 as __acl_internal_bit,__ac_library_rs_parted_internal_type_traits_0_1_0 as __acl_internal_type_traits};}
        pub mod hld {}
    }
}
yukicoder

結果

テストケース

ソースコード
