pub use __cargo_equip::prelude::*; use graph::Graph; #[allow(unused_imports)] use proconio::{ input, marker::{Bytes, Chars, Usize1}, }; use static_top_tree_dp::{StaticTopTreeDP, TreeDPOperator}; enum Op {} impl TreeDPOperator for Op { type V = bool; type E = i64; type Path = Result<(i64, i64, i64, i64), i64>; type Point = Option<(i64, i64)>; fn vertex(&v: &Self::V) -> Self::Path { if v { Ok((0, 0, 0, 0)) } else { Err(0) } } fn add_vertex(&d: &Self::Point, &v: &Self::V) -> Self::Path { match (d, v) { (Some((s, d)), true) => Ok((s + d, 0, 0, 0)), (Some((s, d)), false) => Ok((s, d, 0, 0)), (None, true) => Ok((0, 0, 0, 0)), (None, false) => Err(0), } } fn add_edge(&d: &Self::Path, &e: &Self::E) -> Self::Point { if let Ok((s, d, _, _)) = d { Some((s, d + e)) } else { None } } fn rake(&l: &Self::Point, &r: &Self::Point) -> Self::Point { print!("!"); match (l, r) { (Some((ls, ld)), Some((rs, rd))) => Some((ls + rs + ld + rd, 0)), (Some((ls, ld)), None) => Some((ls, ld)), (None, Some((rs, rd))) => Some((rs, rd)), (None, None) => None, } } fn compress(&p: &Self::Path, &c: &Self::Path, &e: &Self::E) -> Self::Path { match (p, c) { (Ok((ps, pa, pb, pc)), Ok((cs, ca, cb, cc))) => { Ok((ps + cs + e + pa + pb + ca + cc, 0, cb, pc)) } (Ok((ps, pa, pb, pc)), Err(ch)) => Ok((ps, pa, pb + ch + e, pc)), (Err(ph), Ok((cs, ca, cb, cc))) => Ok((cs, ca, cb, cc + ph + e)), (Err(ph), Err(ch)) => Err(ph + ch + e), } } } fn main() { input! { n: usize, uvw: [(usize, usize, i64); n - 1], q: usize, } let g = Graph::from_vertices_and_undirected_edges(&vec![false; n], &uvw); let mut stt = StaticTopTreeDP::::new(&g); for _ in 0..q { input! { x: [usize], } for &x in &x { stt.set_vertex(x, true); } let res = stt.prod().unwrap().0; println!("{}", res); for &x in &x { stt.set_vertex(x, false); } } } // The following code was expanded by `cargo-equip`. /// # Bundled libraries /// /// - `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` /// - `static-top-tree-dp 0.1.0 (path+████████████████████████████████████████████████████████████)` published in **missing** licensed under `CC0-1.0` as `crate::__cargo_equip::crates::static_top_tree_dp` #[cfg_attr(any(), rustfmt::skip)] #[allow(unused)] mod __cargo_equip { pub(crate) mod crates { pub mod graph {use std::ops::Index;#[derive(Clone)]pub struct Graphwhere V:Clone,E:Clone,{vertices:Vec,edges:Vec<(usize,E)>,pos:Vec,edge_id:Vec,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),];implGraphwhere 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>,neighbours:&[(usize,usize)],cost:impl Fn(&V,&V)->Option,)->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::>(),&edges,)}}implIndexfor Graphwhere V:Clone,E:Clone,{type Output=[(usize,E)];fn index(&self,v:usize)->&[(usize,E)]{self.edges(v)}}implGraph<(),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)}}implGraphwhere 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::>(),)}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::>(),)}}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::>(),)}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::>(),)}}} pub mod heavy_light_decomposition {use crate::__cargo_equip::preludes::heavy_light_decomposition::*;use graph::Graph;use std::mem::swap;pub struct HeavyLightDecomposition{pub t_in:Vec,pub t_out:Vec,pub ord:Vec,pub size:Vec,pub heavy:Vec,pub head:Vec,pub par:Vec,pub depth:Vec,}impl HeavyLightDecomposition{pub fn new(g:&Graph)->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(&mut self,g:&Graph,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(&mut self,g:&Graph,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]=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](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]+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 static_top_tree_dp {use crate::__cargo_equip::preludes::static_top_tree_dp::*;use graph::Graph;use heavy_light_decomposition::HeavyLightDecomposition;#[derive(Clone,Copy)]enum Type{Vertex,Compress,Rake,AddEdge,AddVertex,}pub struct StaticTopTree{stt_root:usize,par:Vec,lch:Vec,rch:Vec,ty:Vec,edge:Vec,par_edge:Vec,child:Vec,cnt:usize,}impl StaticTopTree{pub fn new(g:&Graph)->Self{let n=g.len();let mut s=Self{stt_root:!0,par:vec![!0;n*4],lch:vec![!0;n*4],rch:vec![!0;n*4],ty:vec![Type::Vertex;n*4],edge:vec![!0;n*4],par_edge:vec![!0;n],child:vec![!0;n-1],cnt:n,};let hld=HeavyLightDecomposition::new(g);for v in 0..n{for i in 0..g[v].len(){let(u,_)=g[v][i];if hld.depth[v]usize{self.cnt}fn add(&mut self,mut k:usize,l:usize,r:usize,t:Type)->usize{if k==!0{k=self.cnt;self.cnt+=1;}self.par[k]=!0;self.lch[k]=l;self.rch[k]=r;self.ty[k]=t;if l!=!0{self.par[l]=k;}if r!=!0{self.par[r]=k;}k}fn merge(&mut self,a:&[(usize,usize)],t:Type)->(usize,usize){if a.len()==1{return a[0];}let mut u=a.iter().map(|&(_,s)|s).sum::();let mut m=0;while m{self.edge[res.0]=self.par_edge[a[m].0];}_=>(),}res}fn compress(&mut self,mut i:usize,g:&Graph,hld:&HeavyLightDecomposition,)->(usize,usize){let mut chs=vec![self.add_vertex(i,g,hld)];while hld.heavy[i]!=!0{i=hld.heavy[i];chs.push(self.add_vertex(i,g,hld));}self.merge(&chs,Type::Compress)}fn rake(&mut self,i:usize,g:&Graph,hld:&HeavyLightDecomposition,)->(usize,usize){let mut chs=vec![];for&(u,_)in&g[i]{if u==hld.par[i]||u==hld.heavy[i]{continue;}chs.push(self.add_edge(u,g,hld));}if chs.is_empty(){(!0,0)}else{self.merge(&chs,Type::Rake)}}fn add_edge(&mut self,i:usize,g:&Graph,hld:&HeavyLightDecomposition,)->(usize,usize){let(j,sj)=self.compress(i,g,hld);let res=(self.add(!0,j,!0,Type::AddEdge),sj);self.edge[res.0]=self.par_edge[i];res}fn add_vertex(&mut self,i:usize,g:&Graph,hld:&HeavyLightDecomposition,)->(usize,usize){let(j,sj)=self.rake(i,g,hld);(self.add(i,j,!0,if j==!0{Type::Vertex}else{Type::AddVertex},),sj+1,)}}#[derive(Clone)]enum Data{Path(Path),Point(Point),}implData{fn unwrap_path(&self)->&Path{match self{Data::Path(p)=>p,_=>panic!(),}}fn unwrap_point(&self)->&Point{match self{Data::Point(p)=>p,_=>panic!(),}}}pub trait TreeDPOperator{type Path:Clone;type Point:Clone;type V:Clone;type E:Clone;fn vertex(v:&Self::V)->Self::Path;fn compress(p:&Self::Path,c:&Self::Path,e:&Self::E)->Self::Path;fn rake(l:&Self::Point,r:&Self::Point)->Self::Point;fn add_edge(d:&Self::Path,e:&Self::E)->Self::Point;fn add_vertex(d:&Self::Point,v:&Self::V)->Self::Path;}pub struct StaticTopTreeDP{stt:StaticTopTree,sum:Vec>,vertex:Vec,edge:Vec,op:std::marker::PhantomData,}implStaticTopTreeDP{pub fn new(g:&Graph)->Self{let stt=StaticTopTree::new(g);let mut sum=vec![Data::Path(O::vertex(&g.vertex(0)));stt.len()];let vertex=(0..g.len()).map(|v|g.vertex(v).clone()).collect::>();let mut edge=if g.len()==1{vec![]}else{vec![g[0][0].1.clone();g.len()-1]};for v in 0..g.len(){sum[v]=Data::Path(O::vertex(&g.vertex(v)));for i in 0..g[v].len(){edge[g.edge_id(v,i)]=g[v][i].1.clone();}}let mut s=Self{stt,sum,vertex,edge,op:std::marker::PhantomData,};s.dfs(s.stt.stt_root);s}pub fn prod(&self)->O::Path{self.sum[self.stt.stt_root].unwrap_path().clone()}pub fn set_vertex(&mut self,mut v:usize,x:O::V){self.vertex[v]=x.clone();while v!=!0{self.update(v);v=self.stt.par[v];}}pub fn set_edge(&mut self,e:usize,x:O::E){self.edge[e]=x.clone();let mut v=self.stt.child[e];while v!=!0{self.update(v);v=self.stt.par[v];}}fn dfs(&mut self,v:usize){if self.stt.lch[v]!=!0{self.dfs(self.stt.lch[v]);}if self.stt.rch[v]!=!0{self.dfs(self.stt.rch[v]);}self.update(v);}fn update(&mut self,v:usize){match self.stt.ty[v]{Type::Vertex=>{self.sum[v]=Data::Path(O::vertex(&self.vertex[v]));}Type::Compress=>{self.sum[v]=Data::Path(O::compress(self.sum[self.stt.lch[v]].unwrap_path(),self.sum[self.stt.rch[v]].unwrap_path(),&self.edge[self.stt.edge[v]],));}Type::Rake=>{self.sum[v]=Data::Point(O::rake(self.sum[self.stt.lch[v]].unwrap_point(),self.sum[self.stt.rch[v]].unwrap_point(),));}Type::AddEdge=>{self.sum[v]=Data::Point(O::add_edge(self.sum[self.stt.lch[v]].unwrap_path(),&self.edge[self.stt.edge[v]],));}Type::AddVertex=>{self.sum[v]=Data::Path(O::add_vertex(self.sum[self.stt.lch[v]].unwrap_point(),&self.vertex[v],));}}}}} } pub(crate) mod macros { pub mod graph {} pub mod heavy_light_decomposition {} pub mod static_top_tree_dp {} } pub(crate) mod prelude {pub use crate::__cargo_equip::crates::*;} mod preludes { pub mod graph {} pub mod heavy_light_decomposition {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::graph;} pub mod static_top_tree_dp {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::{graph,heavy_light_decomposition};} } }