結果

問題 No.2642 Don't cut line!
ユーザー 37kt37kt
提出日時 2024-04-18 13:18:34
言語 Rust
(1.77.0 + proconio)
結果
AC  
実行時間 108 ms / 4,000 ms
コード長 20,698 bytes
コンパイル時間 15,355 ms
コンパイル使用メモリ 379,212 KB
実行使用メモリ 34,244 KB
最終ジャッジ日時 2024-10-10 06:31:04
合計ジャッジ時間 18,048 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 105 ms
32,452 KB
testcase_02 AC 108 ms
34,244 KB
testcase_03 AC 82 ms
32,456 KB
testcase_04 AC 73 ms
31,552 KB
testcase_05 AC 76 ms
33,352 KB
testcase_06 AC 47 ms
10,628 KB
testcase_07 AC 48 ms
10,864 KB
testcase_08 AC 47 ms
10,652 KB
testcase_09 AC 47 ms
10,792 KB
testcase_10 AC 47 ms
10,864 KB
testcase_11 AC 46 ms
10,780 KB
testcase_12 AC 48 ms
10,952 KB
testcase_13 AC 47 ms
10,648 KB
testcase_14 AC 47 ms
10,692 KB
testcase_15 AC 49 ms
10,948 KB
testcase_16 AC 32 ms
11,520 KB
testcase_17 AC 61 ms
28,548 KB
testcase_18 AC 67 ms
28,084 KB
testcase_19 AC 48 ms
22,316 KB
testcase_20 AC 42 ms
12,944 KB
testcase_21 AC 27 ms
10,380 KB
testcase_22 AC 23 ms
8,600 KB
testcase_23 AC 75 ms
32,876 KB
testcase_24 AC 35 ms
12,668 KB
testcase_25 AC 41 ms
11,880 KB
testcase_26 AC 58 ms
10,096 KB
testcase_27 AC 47 ms
23,080 KB
testcase_28 AC 69 ms
30,188 KB
testcase_29 AC 53 ms
9,908 KB
testcase_30 AC 47 ms
11,320 KB
testcase_31 AC 57 ms
25,216 KB
testcase_32 AC 49 ms
10,924 KB
testcase_33 AC 1 ms
5,248 KB
testcase_34 AC 1 ms
5,248 KB
testcase_35 AC 1 ms
5,248 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

pub use __cargo_equip::prelude::*;

use algebraic::{algebra, monoid};
use chminmax::chmax;
use graph::Graph;
#[allow(unused_imports)]
use proconio::{
    input,
    marker::{Bytes, Chars, Usize1},
};
use tree_query::TreeQueryEdge;
use union_find::UnionFind;

algebra!(M, usize);
monoid!(M, 0, |&a: &usize, &b: &usize| a.max(b));

fn main() {
    input! {
        n: usize,
        m: usize,
        c: usize,
        mut es: [(Usize1, Usize1, usize, usize); m],
    }
    let mut sum = 0;
    let mut mx = 0;
    let mut es1 = vec![];
    let mut es2 = vec![];
    let mut uf = UnionFind::new(n);
    es.sort_by_key(|&(_, _, w, _)| w);
    for (u, v, w, p) in es {
        if uf.merge(u, v) {
            sum += w;
            chmax!(mx, p);
            es1.push((u, v, w));
        } else {
            es2.push((u, v, w, p));
        }
    }
    if sum > c {
        println!("-1");
        return;
    }
    let g = Graph::from_undirected_edges(n, &es1);
    let tq = TreeQueryEdge::<M>::build(&g);
    for (u, v, w, p) in es2 {
        if sum - tq.prod_path(u, v) + w <= c {
            chmax!(mx, p);
        }
    }
    println!("{}", mx);
}

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

///  # Bundled libraries
/// 
///  - `algebraic 0.1.0 (path+████████████████████████████████████████████████████████)`                                      published in **missing** licensed under `CC0-1.0` as `crate::__cargo_equip::crates::algebraic`
///  - `chminmax 0.1.0 (path+████████████████████████████████████████████████████)`                                           published in **missing** licensed under `CC0-1.0` as `crate::__cargo_equip::crates::chminmax`
///  - `graph 0.1.0 (path+████████████████████████████████████████████████)`                                                  published in **missing** licensed under `CC0-1.0` as `crate::__cargo_equip::crates::graph`
///  - `heavy-light-decomposition 0.1.0 (path+█████████████████████████████████████████████████████████████████████████████)` published in **missing** licensed under `CC0-1.0` as `crate::__cargo_equip::crates::heavy_light_decomposition`
///  - `segment-tree 0.1.0 (path+████████████████████████████████████████████████████████████████)`                           published in **missing** licensed under `CC0-1.0` as `crate::__cargo_equip::crates::segment_tree`
///  - `tree-query 0.1.0 (path+██████████████████████████████████████████████████████████████)`                               published in **missing** licensed under `CC0-1.0` as `crate::__cargo_equip::crates::tree_query`
///  - `union-find 0.1.0 (path+██████████████████████████████████████████████████████████████)`                               published in **missing** licensed under `CC0-1.0` as `crate::__cargo_equip::crates::union_find`
#[cfg_attr(any(), rustfmt::skip)]
#[allow(unused)]
mod __cargo_equip {
    pub(crate) mod crates {
        pub mod algebraic {pub use crate::__cargo_equip::macros::algebraic::*;pub trait Algebra{type S;}pub trait Act:Algebra{type X;fn act(f:&Self::S,x:&Self::X)->Self::X;}pub trait Monoid:Algebra{fn e()->Self::S;fn op(x:&Self::S,y:&Self::S)->Self::S;}pub trait Group:Monoid{fn inv(x:&Self::S)->Self::S;}pub trait Zero{fn zero()->Self;fn is_zero(&self)->bool;}pub trait One{fn one()->Self;fn is_one(&self)->bool;}#[macro_export]macro_rules!__cargo_equip_macro_def_algebraic_algebra{($ident:ident,$ty:ty)=>{#[derive(Clone)]enum$ident{}impl$crate::__cargo_equip::crates::algebraic::Algebra for$ident{type S=$ty;}};}macro_rules!algebra{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_algebraic_algebra!{$($tt)*})}#[macro_export]macro_rules!__cargo_equip_macro_def_algebraic_act{($ident:ident,$tar:ty,$act:expr)=>{impl$crate::__cargo_equip::crates::algebraic::Act for$ident{type X=$tar;#[inline]fn act(f:&Self::S,x:&Self::X)->Self::X{$act(f,x)}}};}macro_rules!act{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_algebraic_act!{$($tt)*})}#[macro_export]macro_rules!__cargo_equip_macro_def_algebraic_monoid{($ident:ident,$e:expr,$op:expr)=>{impl$crate::__cargo_equip::crates::algebraic::Monoid for$ident{#[inline]fn e()->Self::S{$e}#[inline]fn op(x:&Self::S,y:&Self::S)->Self::S{$op(x,y)}}};}macro_rules!monoid{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_algebraic_monoid!{$($tt)*})}#[macro_export]macro_rules!__cargo_equip_macro_def_algebraic_group{($ident:ident,$e:expr,$op:expr,$inv:expr)=>{impl$crate::__cargo_equip::crates::algebraic::Monoid for$ident{#[inline]fn e()->Self::S{$e}#[inline]fn op(x:&Self::S,y:&Self::S)->Self::S{$op(x,y)}}impl$crate::__cargo_equip::crates::algebraic::Group for$ident{#[inline]fn inv(x:&Self::S)->Self::S{$inv(x)}}};}macro_rules!group{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_algebraic_group!{$($tt)*})}macro_rules!impl_zero_one{($($t:ty)*)=>{$(impl$crate::__cargo_equip::crates::algebraic::Zero for$t{fn zero()->Self{0}fn is_zero(&self)->bool{*self==0}}impl$crate::__cargo_equip::crates::algebraic::One for$t{fn one()->Self{1}fn is_one(&self)->bool{*self==1}})*};}impl_zero_one!(usize u8 u16 u32 u64 u128 isize i8 i16 i32 i64 i128);}
        pub mod chminmax {pub use crate::__cargo_equip::macros::chminmax::*;#[macro_export]macro_rules!__cargo_equip_macro_def_chminmax_min{($a:expr$(,)*)=>{{$a}};($a:expr,$b:expr$(,)*)=>{{std::cmp::min($a,$b)}};($a:expr,$($rest:expr),+$(,)*)=>{{std::cmp::min($a,$crate::__cargo_equip::crates::chminmax::min!($($rest),+))}};}macro_rules!min{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_chminmax_min!{$($tt)*})}#[macro_export]macro_rules!__cargo_equip_macro_def_chminmax_max{($a:expr$(,)*)=>{{$a}};($a:expr,$b:expr$(,)*)=>{{std::cmp::max($a,$b)}};($a:expr,$($rest:expr),+$(,)*)=>{{std::cmp::max($a,$crate::__cargo_equip::crates::chminmax::max!($($rest),+))}};}macro_rules!max{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_chminmax_max!{$($tt)*})}#[macro_export]macro_rules!__cargo_equip_macro_def_chminmax_chmin{($base:expr,$($cmps:expr),+$(,)*)=>{{let cmp_min=$crate::__cargo_equip::crates::chminmax::min!($($cmps),+);if$base>cmp_min{$base=cmp_min;true}else{false}}};}macro_rules!chmin{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_chminmax_chmin!{$($tt)*})}#[macro_export]macro_rules!__cargo_equip_macro_def_chminmax_chmax{($base:expr,$($cmps:expr),+$(,)*)=>{{let cmp_max=$crate::__cargo_equip::crates::chminmax::max!($($cmps),+);if$base<cmp_max{$base=cmp_max;true}else{false}}};}macro_rules!chmax{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_chminmax_chmax!{$($tt)*})}}
        pub mod graph {use std::ops::Index;#[derive(Clone)]pub struct Graph<V,E>where V:Clone,E:Clone,{vertices:Vec<V>,edges:Vec<(usize,E)>,pos:Vec<usize>,edge_id:Vec<usize>,edges_count:usize,}pub const GRID_NEIGHBOURS_4:&[(usize,usize)]=&[(!0,0),(0,!0),(1,0),(0,1)];pub const GRID_NEIGHBOURS_8:&[(usize,usize)]=&[(!0,0),(0,!0),(1,0),(0,1),(!0,!0),(!0,1),(1,!0),(1,1),];impl<V,E>Graph<V,E>where V:Clone,E:Clone,{pub fn from_vertices_and_directed_edges(vertices:&[V],edges:&[(usize,usize,E)])->Self{if edges.is_empty(){return Self{vertices:vertices.to_vec(),edges:vec![],pos:vec![0;vertices.len()+1],edge_id:vec![],edges_count:0,};}let n=vertices.len();let mut pos=vec![0;n+1];for&(u,_,_)in edges{pos[u]+=1;}for i in 1..=n{pos[i]+=pos[i-1];}let mut ord=vec![0;edges.len()];for i in(0..edges.len()).rev(){let u=edges[i].0;pos[u]-=1;ord[pos[u]]=i;}Self{vertices:vertices.to_vec(),edge_id:ord.clone(),edges:ord.into_iter().map(|i|(edges[i].1,edges[i].2.clone())).collect(),pos,edges_count:edges.len(),}}pub fn from_vertices_and_undirected_edges(vertices:&[V],edges:&[(usize,usize,E)])->Self{if edges.is_empty(){return Self{vertices:vertices.to_vec(),edges:vec![],pos:vec![0;vertices.len()+1],edge_id:vec![],edges_count:0,};}let n=vertices.len();let mut pos=vec![0;n+1];for&(u,v,_)in edges{pos[u]+=1;pos[v]+=1;}for i in 1..=n{pos[i]+=pos[i-1];}let mut ord=vec![0;edges.len()*2];for i in(0..edges.len()*2).rev(){if i&1==0{let u=edges[i>>1].0;pos[u]-=1;ord[pos[u]]=i;}else{let v=edges[i>>1].1;pos[v]-=1;ord[pos[v]]=i;}}Self{vertices:vertices.to_vec(),edge_id:ord.iter().map(|&i|i/2).collect(),edges:ord.into_iter().map(|i|{(if i&1==0{edges[i>>1].1}else{edges[i>>1].0},edges[i>>1].2.clone(),)}).collect(),pos,edges_count:edges.len(),}}pub fn len(&self)->usize{self.vertices.len()}pub fn edges_count(&self)->usize{self.edges_count}pub fn vertex(&self,v:usize)->&V{&self.vertices[v]}pub fn edges(&self,v:usize)->&[(usize,E)]{let l=self.pos[v];let r=self.pos[v+1];&self.edges[l..r]}pub fn edge_id(&self,v:usize,i:usize)->usize{self.edge_id[self.pos[v]+i]}pub fn from_grid(grid:&Vec<Vec<V>>,neighbours:&[(usize,usize)],cost:impl Fn(&V,&V)->Option<E>,)->Self{let h=grid.len();let w=grid[0].len();let mut edges=vec![];for i in 0..h{for j in 0..w{for&(di,dj)in neighbours{let ni=i.wrapping_add(di);let nj=j.wrapping_add(dj);if ni>=h||nj>=w{continue;}if let Some(c)=cost(&grid[i][j],&grid[ni][nj]){edges.push((i*w+j,ni*w+nj,c));}}}}Self::from_vertices_and_directed_edges(&grid.into_iter().flatten().cloned().collect::<Vec<_>>(),&edges,)}}impl<V,E>Index<usize>for Graph<V,E>where V:Clone,E:Clone,{type Output=[(usize,E)];fn index(&self,v:usize)->&[(usize,E)]{self.edges(v)}}impl<E>Graph<(),E>where E:Clone,{pub fn from_directed_edges(n:usize,edges:&[(usize,usize,E)])->Self{Self::from_vertices_and_directed_edges(&vec![();n],edges)}pub fn from_undirected_edges(n:usize,edges:&[(usize,usize,E)])->Self{Self::from_vertices_and_undirected_edges(&vec![();n],edges)}}impl<V>Graph<V,()>where V:Clone,{pub fn from_vertices_and_unweighted_directed_edges(vertices:&[V],edges:&[(usize,usize)],)->Self{Self::from_vertices_and_directed_edges(vertices,&edges.iter().map(|&(u,v)|(u,v,())).collect::<Vec<_>>(),)}pub fn from_vertices_and_unweighted_undirected_edges(vertices:&[V],edges:&[(usize,usize)],)->Self{Self::from_vertices_and_undirected_edges(vertices,&edges.iter().map(|&(u,v)|(u,v,())).collect::<Vec<_>>(),)}}impl Graph<(),()>{pub fn from_unweighted_directed_edges(n:usize,edges:&[(usize,usize)])->Self{Self::from_directed_edges(n,&edges.iter().map(|&(u,v)|(u,v,())).collect::<Vec<_>>(),)}pub fn from_unweighted_undirected_edges(n:usize,edges:&[(usize,usize)])->Self{Self::from_undirected_edges(n,&edges.iter().map(|&(u,v)|(u,v,())).collect::<Vec<_>>(),)}}}
        pub mod heavy_light_decomposition {use crate::__cargo_equip::preludes::heavy_light_decomposition::*;use graph::Graph;use std::mem::swap;pub struct HeavyLightDecomposition{t_in:Vec<usize>,t_out:Vec<usize>,ord:Vec<usize>,size:Vec<usize>,heavy:Vec<usize>,head:Vec<usize>,par:Vec<usize>,depth:Vec<usize>,}impl HeavyLightDecomposition{pub fn new<V,E>(g:&Graph<V,E>)->Self where V:Clone,E:Clone,{let n=g.len();let mut hld=HeavyLightDecomposition{t_in:vec![0;n],t_out:vec![0;n],ord:vec![],size:vec![0;n],heavy:vec![!0;n],head:vec![0;n],par:vec![!0;n],depth:vec![0;n],};hld.dfs_sz(g,0);hld.dfs_hld(g,0,&mut 0);hld}fn dfs_sz<V,E>(&mut self,g:&Graph<V,E>,v:usize)where V:Clone,E:Clone,{self.size[v]=1;for&(u,_)in&g[v]{if u==self.par[v]{continue;}self.par[u]=v;self.depth[u]=self.depth[v]+1;self.dfs_sz(g,u);self.size[v]+=self.size[u];if self.heavy[v]==!0||self.size[u]>self.size[self.heavy[v]]{self.heavy[v]=u;}}}fn dfs_hld<V,E>(&mut self,g:&Graph<V,E>,v:usize,t:&mut usize)where V:Clone,E:Clone,{self.t_in[v]=*t;self.ord.push(v);*t+=1;if self.heavy[v]!=!0{let u=self.heavy[v];self.head[u]=self.head[v];self.dfs_hld(g,u,t);}for&(u,_)in&g[v]{if u==self.par[v]{continue;}if u==self.heavy[v]{continue;}self.head[u]=u;self.dfs_hld(g,u,t);}self.t_out[v]=*t;}}impl HeavyLightDecomposition{pub fn kth_ancestor(&self,mut v:usize,mut k:usize)->usize{if self.depth[v]<k{return!0;}loop{let u=self.head[v];if self.t_in[v]-k>=self.t_in[u]{return self.ord[self.t_in[v]-k];}k-=1+self.t_in[v]-self.t_in[u];v=self.par[u];}}pub fn lca(&self,mut u:usize,mut v:usize)->usize{loop{if self.t_in[u]>self.t_in[v]{swap(&mut u,&mut v);}if self.head[u]==self.head[v]{return u;}v=self.par[self.head[v]];}}pub fn dist(&self,u:usize,v:usize)->usize{let l=self.lca(u,v);self.depth[u]+self.depth[v]-self.depth[l]*2}pub fn jump(&self,u:usize,v:usize,k:usize)->usize{if k==0{return u;}let l=self.lca(u,v);let d_lu=self.depth[u]-self.depth[l];let d_lv=self.depth[v]-self.depth[l];if k>d_lu+d_lv{!0}else if k<=d_lu{self.kth_ancestor(u,k)}else{self.kth_ancestor(v,d_lu+d_lv-k)}}pub fn vertex(&self,v:usize)->usize{self.t_in[v]}pub fn edge(&self,u:usize,v:usize)->usize{if self.depth[u]<self.depth[v]{self.t_in[v]}else{self.t_in[u]}}pub fn path(&self,mut u:usize,mut v:usize,edge:bool,)->(Vec<(usize,usize)>,Vec<(usize,usize)>){let mut up=vec![];let mut down=vec![];let e=if edge{1}else{0};while self.head[u]!=self.head[v]{if self.t_in[u]<self.t_in[v]{down.push((self.t_in[self.head[v]],self.t_in[v]+1));v=self.par[self.head[v]];}else{up.push((self.t_in[self.head[u]],self.t_in[u]+1));u=self.par[self.head[u]];}}if self.t_in[u]<self.t_in[v]{down.push((self.t_in[u]+e,self.t_in[v]+1));}else if self.t_in[u]>=self.t_in[v]+e{up.push((self.t_in[v]+e,self.t_in[u]+1));}down.reverse();(up,down)}pub fn subtree(&self,v:usize,edge:bool)->(usize,usize){let e=if edge{1}else{0};(self.t_in[v]+e,self.t_out[v])}}}
        pub mod segment_tree {use crate::__cargo_equip::preludes::segment_tree::*;use std::ops::{Bound,RangeBounds};use algebraic::Monoid;#[derive(Clone)]pub struct SegmentTree<M>where M:Monoid,M::S:Clone,{n:usize,v:Vec<M::S>,}impl<M>SegmentTree<M>where M:Monoid,M::S:Clone,{pub fn new(n:usize)->Self{Self{n,v:vec![M::e();n*2],}}pub fn set(&mut self,mut k:usize,x:M::S){k+=self.n;self.v[k]=x;while k>1{k>>=1;self.v[k]=M::op(&self.v[k*2],&self.v[k*2+1]);}}pub fn get(&self,k:usize)->M::S{assert!(k<self.n);self.v[k+self.n].clone()}pub fn prod<R>(&self,range:R)->M::S where R:RangeBounds<usize>,{let mut l=match range.start_bound(){Bound::Excluded(&l)=>l+1,Bound::Included(&l)=>l,Bound::Unbounded=>0,};let mut r=match range.end_bound(){Bound::Excluded(&r)=>r,Bound::Included(&r)=>r+1,Bound::Unbounded=>self.n,};assert!(l<=r);assert!(r<=self.n);l+=self.n;r+=self.n;let mut sl=M::e();let mut sr=M::e();while l<r{if l&1!=0{sl=M::op(&sl,&self.v[l]);l+=1;}if r&1!=0{r-=1;sr=M::op(&self.v[r],&sr);}l>>=1;r>>=1;}M::op(&sl,&sr)}pub fn max_right<P>(&self,mut l:usize,pred:P)->usize where P:Fn(&M::S)->bool,{assert!(l<=self.n);assert!(pred(&M::e()));if pred(&self.prod(l..)){return self.n;}l+=self.n;let mut s=M::e();loop{while l&1==0&&self.is_good_node(l>>1){l>>=1;}if!pred(&M::op(&s,&self.v[l])){while l<self.n{l<<=1;let t=M::op(&s,&self.v[l]);if pred(&t){s=t;l+=1;}}return l-self.n;}s=M::op(&s,&self.v[l]);l+=1;}}pub fn min_left<P>(&self,mut r:usize,pred:P)->usize where P:Fn(&M::S)->bool,{assert!(r<=self.n);assert!(pred(&M::e()));if pred(&self.prod(..r)){return 0;}r+=self.n;let mut s=M::e();loop{r-=1;while!self.is_good_node(r){r=r*2+1;}while r&1!=0&&self.is_good_node(r>>1){r>>=1;}if!pred(&M::op(&self.v[r],&s)){while r<self.n{r=r*2+1;let t=M::op(&self.v[r],&s);if pred(&t){s=t;r-=1;}}return r+1-self.n;}s=M::op(&self.v[r],&s);}}#[inline]fn is_good_node(&self,k:usize)->bool{if k>=self.n{true}else{let d=k.leading_zeros()-self.n.leading_zeros();self.n>>d!=k||self.n>>d<<d==self.n}}}impl<M>From<Vec<M::S>>for SegmentTree<M>where M:Monoid,M::S:Clone,{fn from(mut a:Vec<M::S>)->Self{let n=a.len();let mut v=vec![M::e();n];v.append(&mut a);for i in(1..n).rev(){v[i]=M::op(&v[i*2],&v[i*2+1]);}Self{n,v}}}}
        pub mod tree_query {use crate::__cargo_equip::preludes::tree_query::*;use std::marker::PhantomData;use algebraic::Monoid;use graph::Graph;use heavy_light_decomposition::HeavyLightDecomposition;use segment_tree::SegmentTree;pub type TreeQueryVertex<M> =TreeQuery<M,Vertex>;pub type TreeQueryEdge<M> =TreeQuery<M,Edge>;pub trait QueryType{fn vertex()->bool;fn edge()->bool;}pub enum Vertex{}pub enum Edge{}impl QueryType for Vertex{fn vertex()->bool{true}fn edge()->bool{false}}impl QueryType for Edge{fn vertex()->bool{false}fn edge()->bool{true}}pub struct TreeQuery<M,Q>where M:Monoid,M::S:Clone,Q:QueryType,{n:usize,hld:HeavyLightDecomposition,seg_up:SegmentTree<M>,seg_down:SegmentTree<M>,_marker:PhantomData<fn()->Q>,}impl<M,Q>TreeQuery<M,Q>where M:Monoid,M::S:Clone,Q:QueryType,{pub fn prod_path(&self,u:usize,v:usize)->M::S{let(up,down)=self.hld.path(u,v,Q::edge());let mut res=M::e();for&(l,r)in&up{let t=self.seg_up.prod(self.n-r..self.n-l);res=M::op(&res,&t);}for&(l,r)in&down{let t=self.seg_down.prod(l..r);res=M::op(&res,&t);}res}pub fn prod_subtree(&self,v:usize)->M::S{let(l,r)=self.hld.subtree(v,Q::edge());self.seg_down.prod(l..r)}}impl<V,M>TreeQuery<M,Vertex>where V:Clone,M:Monoid<S=V>,{pub fn build<E>(g:&Graph<V,E>)->Self where E:Clone,{let n=g.len();let hld=HeavyLightDecomposition::new(g);let mut a=vec![M::e();n];for v in 0..n{let k=hld.vertex(v);a[k]=g.vertex(v).clone();}let seg_down=SegmentTree::from(a.clone());a.reverse();let seg_up=SegmentTree::from(a);Self{n,hld,seg_up,seg_down,_marker:PhantomData::default(),}}pub fn set(&mut self,v:usize,x:M::S){let k=self.hld.vertex(v);self.seg_up.set(self.n-1-k,x.clone());self.seg_down.set(k,x);}pub fn get(&self,v:usize)->M::S{let k=self.hld.vertex(v);self.seg_down.get(k)}}impl<E,M>TreeQuery<M,Edge>where E:Clone,M:Monoid<S=E>,{pub fn build<V>(g:&Graph<V,E>)->Self where V:Clone,{let n=g.len();let hld=HeavyLightDecomposition::new(g);let mut a=vec![M::e();n];for v in 0..n{for(u,w)in&g[v]{let k=hld.edge(*u,v);a[k]=w.clone();}}let seg_down=SegmentTree::from(a.clone());a.reverse();let seg_up=SegmentTree::from(a);Self{n,hld,seg_up,seg_down,_marker:PhantomData::default(),}}pub fn set(&mut self,u:usize,v:usize,x:M::S){let k=self.hld.edge(u,v);self.seg_up.set(self.n-1-k,x.clone());self.seg_down.set(k,x);}pub fn get(&self,u:usize,v:usize)->M::S{let k=self.hld.edge(u,v);self.seg_down.get(k)}}}
        pub mod union_find {use std::{cell::RefCell,mem::swap};#[derive(Clone)]pub struct UnionFind{par:RefCell<Vec<i32>>,}impl UnionFind{pub fn new(n:usize)->Self{Self{par:RefCell::new(vec![-1;n]),}}pub fn len(&self)->usize{self.par.borrow().len()}pub fn merge(&mut self,x:usize,y:usize)->bool{let mut x=self.leader(x);let mut y=self.leader(y);if x==y{return false;}let mut par=self.par.borrow_mut();if-par[x]< -par[y]{swap(&mut x,&mut y);}par[x]+=par[y];par[y]=x as i32;true}pub fn leader(&self,x:usize)->usize{let mut v=x;let mut par=self.par.borrow_mut();while par[v]>=0{v=par[v]as usize;}let mut u=x;while par[u]>=0{let t=par[u]as usize;par[u]=v as i32;u=t;}u}pub fn same(&self,x:usize,y:usize)->bool{self.leader(x)==self.leader(y)}pub fn size(&self,x:usize)->usize{let x=self.leader(x);-self.par.borrow()[x]as usize}pub fn groups(&self)->Vec<Vec<usize>>{let mut res=vec![vec![];self.len()];for x in 0..self.len(){res[self.leader(x)].push(x);}res.into_iter().filter(|g|g.len()>0).collect()}}}
    }

    pub(crate) mod macros {
        pub mod algebraic {pub use crate::{__cargo_equip_macro_def_algebraic_act as act,__cargo_equip_macro_def_algebraic_algebra as algebra,__cargo_equip_macro_def_algebraic_group as group,__cargo_equip_macro_def_algebraic_monoid as monoid};}
        pub mod chminmax {pub use crate::{__cargo_equip_macro_def_chminmax_chmax as chmax,__cargo_equip_macro_def_chminmax_chmin as chmin,__cargo_equip_macro_def_chminmax_max as max,__cargo_equip_macro_def_chminmax_min as min};}
        pub mod graph {}
        pub mod heavy_light_decomposition {}
        pub mod segment_tree {}
        pub mod tree_query {}
        pub mod union_find {}
    }

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

    mod preludes {
        pub mod algebraic {}
        pub mod chminmax {}
        pub mod graph {}
        pub mod heavy_light_decomposition {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::graph;}
        pub mod segment_tree {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::algebraic;}
        pub mod tree_query {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::{algebraic,graph,heavy_light_decomposition,segment_tree};}
        pub mod union_find {}
    }
}
0