結果
問題 | No.2892 Lime and Karin |
ユーザー | vwxyz |
提出日時 | 2024-09-13 23:15:30 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 3,463 ms / 8,000 ms |
コード長 | 62,684 bytes |
コンパイル時間 | 343 ms |
コンパイル使用メモリ | 90,368 KB |
実行使用メモリ | 297,684 KB |
最終ジャッジ日時 | 2024-09-13 23:17:04 |
合計ジャッジ時間 | 87,281 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 78 ms
68,352 KB |
testcase_01 | AC | 77 ms
68,480 KB |
testcase_02 | AC | 78 ms
68,608 KB |
testcase_03 | AC | 78 ms
68,480 KB |
testcase_04 | AC | 80 ms
69,376 KB |
testcase_05 | AC | 83 ms
69,376 KB |
testcase_06 | AC | 100 ms
76,800 KB |
testcase_07 | AC | 79 ms
68,992 KB |
testcase_08 | AC | 106 ms
76,928 KB |
testcase_09 | AC | 106 ms
77,184 KB |
testcase_10 | AC | 81 ms
69,760 KB |
testcase_11 | AC | 76 ms
68,736 KB |
testcase_12 | AC | 82 ms
69,632 KB |
testcase_13 | AC | 97 ms
77,056 KB |
testcase_14 | AC | 1,493 ms
159,676 KB |
testcase_15 | AC | 1,430 ms
151,688 KB |
testcase_16 | AC | 2,281 ms
216,152 KB |
testcase_17 | AC | 829 ms
107,412 KB |
testcase_18 | AC | 2,109 ms
218,648 KB |
testcase_19 | AC | 2,699 ms
263,288 KB |
testcase_20 | AC | 587 ms
89,328 KB |
testcase_21 | AC | 1,752 ms
177,588 KB |
testcase_22 | AC | 2,051 ms
206,888 KB |
testcase_23 | AC | 1,073 ms
126,516 KB |
testcase_24 | AC | 2,930 ms
264,296 KB |
testcase_25 | AC | 2,906 ms
272,680 KB |
testcase_26 | AC | 2,929 ms
267,016 KB |
testcase_27 | AC | 2,866 ms
285,788 KB |
testcase_28 | AC | 2,950 ms
269,488 KB |
testcase_29 | AC | 2,981 ms
273,620 KB |
testcase_30 | AC | 2,915 ms
274,520 KB |
testcase_31 | AC | 2,977 ms
283,396 KB |
testcase_32 | AC | 2,881 ms
288,224 KB |
testcase_33 | AC | 2,880 ms
266,360 KB |
testcase_34 | AC | 624 ms
190,960 KB |
testcase_35 | AC | 633 ms
194,544 KB |
testcase_36 | AC | 695 ms
193,140 KB |
testcase_37 | AC | 713 ms
199,024 KB |
testcase_38 | AC | 705 ms
195,048 KB |
testcase_39 | AC | 2,924 ms
297,684 KB |
testcase_40 | AC | 2,887 ms
268,648 KB |
testcase_41 | AC | 3,456 ms
297,048 KB |
testcase_42 | AC | 3,463 ms
264,424 KB |
testcase_43 | AC | 3,336 ms
267,868 KB |
testcase_44 | AC | 1,132 ms
140,464 KB |
testcase_45 | AC | 2,278 ms
243,924 KB |
testcase_46 | AC | 1,302 ms
151,596 KB |
testcase_47 | AC | 1,561 ms
178,780 KB |
testcase_48 | AC | 877 ms
118,660 KB |
testcase_49 | AC | 1,835 ms
198,308 KB |
testcase_50 | AC | 1,764 ms
248,144 KB |
testcase_51 | AC | 1,739 ms
243,440 KB |
testcase_52 | AC | 1,850 ms
240,524 KB |
testcase_53 | AC | 1,934 ms
259,160 KB |
testcase_54 | AC | 1,799 ms
247,520 KB |
ソースコード
import heapq import random from collections import defaultdict,deque class Graph: def __init__(self,V,edges=None,graph=None,directed=False,weighted=False,inf=float("inf")): self.V=V self.directed=directed self.weighted=weighted self.inf=inf if graph!=None: self.graph=graph """ self.edges=[] for i in range(self.V): if self.weighted: for j,d in self.graph[i]: if self.directed or not self.directed and i<=j: self.edges.append((i,j,d)) else: for j in self.graph[i]: if self.directed or not self.directed and i<=j: self.edges.append((i,j)) """ else: self.edges=edges self.graph=[[] for i in range(self.V)] if weighted: for i,j,d in self.edges: self.graph[i].append((j,d)) if not self.directed: self.graph[j].append((i,d)) else: for i,j in self.edges: self.graph[i].append(j) if not self.directed: self.graph[j].append(i) def SIV_DFS(self,s,bipartite_graph=False,cycle_detection=False,directed_acyclic=False,euler_tour=False,linked_components=False,lowlink=False,parents=False,postorder=False,preorder=False,subtree_size=False,topological_sort=False,unweighted_dist=False,weighted_dist=False): seen=[False]*self.V finished=[False]*self.V if directed_acyclic or cycle_detection or topological_sort: dag=True if euler_tour: et=[] if linked_components: lc=[] if lowlink: order=[None]*self.V ll=[None]*self.V idx=0 if parents or cycle_detection or lowlink or subtree_size: ps=[None]*self.V if postorder or topological_sort: post=[] if preorder: pre=[] if subtree_size: ss=[1]*self.V if unweighted_dist or bipartite_graph: uwd=[self.inf]*self.V uwd[s]=0 if weighted_dist: wd=[self.inf]*self.V wd[s]=0 stack=[(s,0)] if self.weighted else [s] while stack: if self.weighted: x,d=stack.pop() else: x=stack.pop() if not seen[x]: seen[x]=True stack.append((x,d) if self.weighted else x) if euler_tour: et.append(x) if linked_components: lc.append(x) if lowlink: order[x]=idx ll[x]=idx idx+=1 if preorder: pre.append(x) for y in self.graph[x]: if self.weighted: y,d=y if not seen[y]: stack.append((y,d) if self.weighted else y) if parents or cycle_detection or lowlink or subtree_size: ps[y]=x if unweighted_dist or bipartite_graph: uwd[y]=uwd[x]+1 if weighted_dist: wd[y]=wd[x]+d elif not finished[y]: if (directed_acyclic or cycle_detection or topological_sort) and dag: dag=False if cycle_detection: cd=(y,x) elif not finished[x]: finished[x]=True if euler_tour: et.append(~x) if lowlink: bl=True for y in self.graph[x]: if self.weighted: y,d=y if ps[x]==y and bl: bl=False continue ll[x]=min(ll[x],order[y]) if x!=s: ll[ps[x]]=min(ll[ps[x]],ll[x]) if postorder or topological_sort: post.append(x) if subtree_size: for y in self.graph[x]: if self.weighted: y,d=y if y==ps[x]: continue ss[x]+=ss[y] if bipartite_graph: bg=[[],[]] for tpl in self.edges: x,y=tpl[:2] if self.weighted else tpl if uwd[x]==self.inf or uwd[y]==self.inf: continue if not uwd[x]%2^uwd[y]%2: bg=False break else: for x in range(self.V): if uwd[x]==self.inf: continue bg[uwd[x]%2].append(x) retu=() if bipartite_graph: retu+=(bg,) if cycle_detection: if dag: cd=[] else: y,x=cd cd=self.Route_Restoration(y,x,ps) retu+=(cd,) if directed_acyclic: retu+=(dag,) if euler_tour: retu+=(et,) if linked_components: retu+=(lc,) if lowlink: retu=(ll,) if parents: retu+=(ps,) if postorder: retu+=(post,) if preorder: retu+=(pre,) if subtree_size: retu+=(ss,) if topological_sort: if dag: tp_sort=post[::-1] else: tp_sort=[] retu+=(tp_sort,) if unweighted_dist: retu+=(uwd,) if weighted_dist: retu+=(wd,) if len(retu)==1: retu=retu[0] return retu def MIV_DFS(self,initial_vertices=None,bipartite_graph=False,cycle_detection=False,directed_acyclic=False,euler_tour=False,linked_components=False,lowlink=False,parents=False,postorder=False,preorder=False,subtree_size=False,topological_sort=False,unweighted_dist=False,weighted_dist=False): if initial_vertices==None: initial_vertices=[s for s in range(self.V)] seen=[False]*self.V finished=[False]*self.V if bipartite_graph: bg=[None]*self.V cnt=-1 if directed_acyclic or cycle_detection or topological_sort: dag=True if euler_tour: et=[] if linked_components: lc=[] if lowlink: order=[None]*self.V ll=[None]*self.V idx=0 if parents or cycle_detection or lowlink or subtree_size: ps=[None]*self.V if postorder or topological_sort: post=[] if preorder: pre=[] if subtree_size: ss=[1]*self.V if bipartite_graph or unweighted_dist: uwd=[self.inf]*self.V if weighted_dist: wd=[self.inf]*self.V for s in initial_vertices: if seen[s]: continue if bipartite_graph: cnt+=1 bg[s]=(cnt,0) if linked_components: lc.append([]) if bipartite_graph or unweighted_dist: uwd[s]=0 if weighted_dist: wd[s]=0 stack=[(s,0)] if self.weighted else [s] while stack: if self.weighted: x,d=stack.pop() else: x=stack.pop() if not seen[x]: seen[x]=True stack.append((x,d) if self.weighted else x) if euler_tour: et.append(x) if linked_components: lc[-1].append(x) if lowlink: order[x]=idx ll[x]=idx idx+=1 if preorder: pre.append(x) for y in self.graph[x]: if self.weighted: y,d=y if not seen[y]: stack.append((y,d) if self.weighted else y) if bipartite_graph: bg[y]=(cnt,bg[x][1]^1) if parents or cycle_detection or lowlink or subtree_size: ps[y]=x if unweighted_dist or bipartite_graph: uwd[y]=uwd[x]+1 if weighted_dist: wd[y]=wd[x]+d elif not finished[y]: if (directed_acyclic or cycle_detection or topological_sort) and dag: dag=False if cycle_detection: cd=(y,x) elif not finished[x]: finished[x]=True if euler_tour: et.append(~x) if lowlink: bl=True for y in self.graph[x]: if self.weighted: y,d=y if ps[x]==y and bl: bl=False continue ll[x]=min(ll[x],order[y]) if x!=s: ll[ps[x]]=min(ll[ps[x]],ll[x]) if postorder or topological_sort: post.append(x) if subtree_size: for y in self.graph[x]: if self.weighted: y,d=y if y==ps[x]: continue ss[x]+=ss[y] if bipartite_graph: bg_=bg bg=[[[],[]] for i in range(cnt+1)] for tpl in self.edges: i,j=tpl[:2] if self.weighted else tpl if not bg_[i][1]^bg_[j][1]: bg[bg_[i][0]]=False for x in range(self.V): if bg[bg_[x][0]]: bg[bg_[x][0]][bg_[x][1]].append(x) retu=() if bipartite_graph: retu+=(bg,) if cycle_detection: if dag: cd=[] else: y,x=cd cd=self.Route_Restoration(y,x,ps) retu+=(cd,) if directed_acyclic: retu+=(dag,) if euler_tour: retu+=(et,) if linked_components: retu+=(lc,) if lowlink: retu=(ll,) if parents: retu+=(ps,) if postorder: retu+=(post,) if preorder: retu+=(pre,) if subtree_size: retu+=(ss,) if topological_sort: if dag: tp_sort=post[::-1] else: tp_sort=[] retu+=(tp_sort,) if unweighted_dist: retu+=(uwd,) if weighted_dist: retu+=(wd,) if len(retu)==1: retu=retu[0] return retu def SIV_BFS(self,s,bfs_tour=False,bipartite_graph=False,linked_components=False,parents=False,unweighted_dist=False,weighted_dist=False): seen=[False]*self.V seen[s]=True if bfs_tour: bt=[s] if linked_components: lc=[s] if parents: ps=[None]*self.V if unweighted_dist or bipartite_graph: uwd=[self.inf]*self.V uwd[s]=0 if weighted_dist: wd=[self.inf]*self.V wd[s]=0 queue=deque([s]) while queue: x=queue.popleft() for y in self.graph[x]: if self.weighted: y,d=y if not seen[y]: seen[y]=True queue.append(y) if bfs_tour: bt.append(y) if linked_components: lc.append(y) if parents: ps[y]=x if unweighted_dist or bipartite_graph: uwd[y]=uwd[x]+1 if weighted_dist: wd[y]=wd[x]+d if bipartite_graph: bg=[[],[]] for tpl in self.edges: i,j=tpl[:2] if self.weighted else tpl if uwd[i]==self.inf or uwd[j]==self.inf: continue if not uwd[i]%2^uwd[j]%2: bg=False break else: for x in range(self.V): if uwd[x]==self.inf: continue bg[uwd[x]%2].append(x) retu=() if bfs_tour: retu+=(bt,) if bipartite_graph: retu+=(bg,) if linked_components: retu+=(lc,) if parents: retu+=(ps,) if unweighted_dist: retu+=(uwd,) if weighted_dist: retu+=(wd,) if len(retu)==1: retu=retu[0] return retu def MIV_BFS(self,initial_vertices=None,bipartite_graph=False,linked_components=False,parents=False,unweighted_dist=False,weighted_dist=False): if initial_vertices==None: initial_vertices=[i for i in range(self.V)] seen=[False]*self.V if bipartite_graph: bg=[None]*self.V cnt=-1 if linked_components: lc=[] if parents: ps=[None]*self.V if unweighted_dist: uwd=[self.inf]*self.V if weighted_dist: wd=[self.inf]*self.V for s in initial_vertices: if seen[s]: continue seen[s]=True if bipartite_graph: cnt+=1 bg[s]=(cnt,0) if linked_components: lc.append([s]) if unweighted_dist: uwd[s]=0 if weighted_dist: wd[s]=0 queue=deque([s]) while queue: x=queue.popleft() for y in self.graph[x]: if self.weighted: y,d=y if not seen[y]: seen[y]=True queue.append(y) if bipartite_graph: bg[y]=(cnt,bg[x][1]^1) if linked_components: lc[-1].append(y) if parents: ps[y]=x if unweighted_dist: uwd[y]=uwd[x]+1 if weighted_dist: wd[y]=wd[x]+d if bipartite_graph: bg_=bg bg=[[[],[]] for i in range(cnt+1)] for tpl in self.edges: i,j=tpl[:2] if self.weighted else tpl if not bg_[i][1]^bg_[j][1]: bg[bg_[i][0]]=False for x in range(self.V): if bg[bg_[x][0]]: bg[bg_[x][0]][bg_[x][1]].append(x) retu=() if bipartite_graph: retu+=(bg,) if linked_components: retu+=(lc,) if parents: retu=(ps,) if unweighted_dist: retu+=(uwd,) if weighted_dist: retu+=(wd,) if len(retu)==1: retu=retu[0] return retu def Tree_Diameter(self,weighted=False): def Farthest_Point(u): dist=self.SIV_DFS(u,weighted_dist=True) if weighted else self.SIV_DFS(u,unweighted_dist=True) fp=0 for i in range(self.V): if dist[fp]<dist[i]: fp=i return fp,dist[fp] u,d=Farthest_Point(0) v,d=Farthest_Point(u) return u,v,d def SCC(self): reverse_graph=[[] for i in range(self.V)] for tpl in self.edges: u,v=tpl[:2] if self.weighted else tpl reverse_graph[v].append(u) postorder=self.MIV_DFS(postorder=True) scc_points=[] seen=[False]*self.V for s in postorder[::-1]: if seen[s]: continue queue=deque([s]) seen[s]=True lst=[] while queue: x=queue.popleft() lst.append(x) for y in reverse_graph[x]: if not seen[y]: seen[y]=True queue.append(y) scc_points.append(lst) l=len(scc_points) idx=[None]*self.V for i in range(l): for x in scc_points[i]: idx[x]=i scc_edges=set() for tpl in self.edges: if self.weighted: u,v,w=tpl else: u,v=tpl if idx[u]!=idx[v]: scc_edges.add((idx[u],idx[v],w) if self.weighted else (idx[u],idx[v])) scc_edges=list(scc_edges) return scc_points,scc_edges def Build_LCA(self,s,segment_tree=False): self.lca_segment_tree=segment_tree if self.lca_segment_tree: self.lca_euler_tour,self.lca_parents,depth=self.SIV_DFS(s,euler_tour=True,parents=True,unweighted_dist=True) self.lca_dfs_in_index=[None]*self.V self.lca_dfs_out_index=[None]*self.V for i,x in enumerate(self.lca_euler_tour): if x>=0: self.lca_dfs_in_index[x]=i else: self.lca_dfs_out_index[~x]=i self.ST=Segment_Tree(2*self.V,min,self.V) lst=[None]*(2*self.V) for i in range(2*self.V-1): if self.lca_euler_tour[i]>=0: lst[i]=depth[self.lca_euler_tour[i]] else: lst[i]=depth[self.lca_parents[~self.lca_euler_tour[i]]] lst[2*self.V-1]=-1 self.ST.Build(lst) else: self.lca_parents,self.lca_depth=self.SIV_DFS(s,parents=True,unweighted_dist=True) self.lca_PD=Path_Doubling(self.V,self.lca_parents) self.lca_PD.Build_Next(self.V) def LCA(self,a,b): if self.lca_segment_tree: m=min(self.lca_dfs_in_index[a],self.lca_dfs_in_index[b]) M=max(self.lca_dfs_in_index[a],self.lca_dfs_in_index[b]) x=self.lca_euler_tour[self.ST.Fold_Index(m,M+1)] if x>=0: lca=x else: lca=self.lca_parents[~x] else: if self.lca_depth[a]>self.lca_depth[b]: a,b=b,a b=self.lca_PD.Permutation_Doubling(b,self.lca_depth[b]-self.lca_depth[a]) if a!=b: for k in range(self.lca_PD.k-1,-1,-1): if self.lca_PD.permutation_doubling[k][a]!=self.lca_PD.permutation_doubling[k][b]: a,b=self.lca_PD.permutation_doubling[k][a],self.lca_PD.permutation_doubling[k][b] a,b=self.lca_PD.permutation_doubling[0][a],self.lca_PD.permutation_doubling[0][b] lca=a return lca def Build_HLD(self,s): self.hld_parents,size,self.hld_depth=self.SIV_DFS(s,parents=True,subtree_size=True,unweighted_dist=True) stack=[s] self.hld_tour=[] self.hld_path_parents=[None]*self.V self.hld_path_parents[s]=s while stack: x=stack.pop() self.hld_tour.append(x) max_size=0 max_size_y=None for y in self.graph[x]: if self.weighted: y,d=y if y==self.hld_parents[x]: continue if max_size<size[y]: max_size=size[y] max_size_y=y for y in self.graph[x]: if self.weighted: y,d=y if y==self.hld_parents[x]: continue if y!=max_size_y: stack.append(y) self.hld_path_parents[y]=y if max_size_y!=None: stack.append(max_size_y) self.hld_path_parents[max_size_y]=self.hld_path_parents[x] self.hld_tour_idx=[None]*self.V for i in range(self.V): self.hld_tour_idx[self.hld_tour[i]]=i def HLD(self,a,b,edge=False): L,R=[],[] while self.hld_path_parents[a]!=self.hld_path_parents[b]: if self.hld_depth[self.hld_path_parents[a]]<self.hld_depth[self.hld_path_parents[b]]: R.append((self.hld_tour_idx[self.hld_path_parents[b]],self.hld_tour_idx[b]+1)) b=self.hld_parents[self.hld_path_parents[b]] else: L.append((self.hld_tour_idx[a]+1,self.hld_tour_idx[self.hld_path_parents[a]])) a=self.hld_parents[self.hld_path_parents[a]] if edge: if self.hld_depth[a]!=self.hld_depth[b]: retu=L+[(self.hld_tour_idx[a]+1,self.hld_tour_idx[b]+1)]+R[::-1] else: retu=L+R[::-1] else: if self.hld_depth[a]<self.hld_depth[b]: retu=L+[(self.hld_tour_idx[a],self.hld_tour_idx[b]+1)]+R[::-1] else: retu=L+[(self.hld_tour_idx[a]+1,self.hld_tour_idx[b])]+R[::-1] return retu def Build_Hash(self,s,random_number=False,mod=(1<<61)-1,rerooting=False): self.lower_hash=[None]*self.V if random_number: self.hash_random_number=random_number else: self.hash_random_number=[random.randint(1,10**10) for i in range(self.V)] self.hash_mod=mod parents,postorder,preorder=self.SIV_DFS(s,parents=True,postorder=True,preorder=True) for x in postorder: level=0 for y in self.graph[x]: if self.weighted: y,d=y if y==parents[x]: continue h,l=self.lower_hash[y] level=max(level,l+1) ha=1 for y in self.graph[x]: if self.weighted: y,d=y if y==parents[x]: continue h,l=self.lower_hash[y] ha*=h+self.hash_random_number[l] ha%=self.hash_mod self.lower_hash[x]=(ha,level) if rerooting: self.upper_hash=[None]*self.V self.upper_hash[s]=(1,-1) for x in preorder: children=[y for y,d in self.graph[x] if y!=parents[x]] if self.weighted else [y for y in self.graph[x] if y!=parents[x]] if children: l=len(children) l_lst,r_lst=[None]*(l+1),[None]*(l+1) l_lst[0],r_lst[l]=(1,-1),(1,-1) for i in range(1,l+1): h0,l0=l_lst[i-1] h1,l1=self.lower_hash[children[i-1]] l_lst[i]=(h0*(h1+self.hash_random_number[l1])%self.hash_mod,max(l0,l1)) for i in range(l-1,-1,-1): h0,l0=r_lst[i+1] h1,l1=self.lower_hash[children[i]] r_lst[i]=(h0*(h1+self.hash_random_number[l1])%self.hash_mod,max(l0,l1)) for i in range(l): if x==s: ha,level=1,0 else: ha,level=self.upper_hash[x] h0,l0=l_lst[i] h1,l1=r_lst[i+1] ha*=h0*h1 level=max(level,l0+1,l1+1) ha+=self.hash_random_number[level] ha%=self.hash_mod level+=1 self.upper_hash[children[i]]=(ha,level) return def Hash(self,root,subtree=False): if subtree: ha,level=self.lower_hash[root] ha+=self.hash_random_number[level] ha%=self.hash_mod else: h0,l0=self.lower_hash[root] h1,l1=self.upper_hash[root] ha=(h0*h1+self.hash_random_number[max(l0,l1)])%self.hash_mod level=max(l0,l1) return ha,level def Build_Rerooting(self,s,f,f_merge,subtree=False): self.rerooting_s=s self.rerooting_f=f self.rerooting_f_merge=f_merge self.subtree=subtree if self.subtree: parents,postorder,preorder,self.rerooting_depth=self.SIV_DFS(s,parents=True,postorder=True,preorder=True,unweighted_dist=True) parents[s]=s self.rerooting_PD=Path_Doubling(self.V,parents) self.rerooting_PD.Build_Next() parents[s]=None else: parents,postorder,preorder=self.SIV_DFS(s,parents=True,postorder=True,preorder=True) self.rerooting_lower_dp=[None]*self.V for x in postorder: children=[y[0] if self.weighted else y for y in self.graph[x] if (y[0] if self.weighted else y)!=parents[x]] self.rerooting_lower_dp[x]=self.rerooting_f_merge(x,[self.rerooting_f(y,self.rerooting_lower_dp[y]) for y in children]) self.rerooting_upper_dp=[None]*self.V for x in preorder: children=[y[0] if self.weighted else y for y in self.graph[x] if (y[0] if self.weighted else y)!=parents[x]] left_accumule_f=[None]*(len(children)+1) right_accumule_f=[None]*(len(children)+1) left_accumule_f[0]=self.rerooting_f_merge(x,[]) for i in range(1,len(children)+1): left_accumule_f[i]=self.rerooting_f_merge(x,[left_accumule_f[i-1],self.rerooting_f(children[i-1],self.rerooting_lower_dp[children[i-1]])]) right_accumule_f[len(children)]=self.rerooting_f_merge(x,[]) for i in range(len(children)-1,-1,-1): right_accumule_f[i]=self.rerooting_f_merge(x,[right_accumule_f[i+1],self.rerooting_f(children[i],self.rerooting_lower_dp[children[i]])]) for i in range(len(children)): if parents[x]==None: self.rerooting_upper_dp[children[i]]=self.rerooting_f(x,self.rerooting_f_merge(x,[left_accumule_f[i],right_accumule_f[i+1]])) else: self.rerooting_upper_dp[children[i]]=self.rerooting_f(x,self.rerooting_f_merge(x,[left_accumule_f[i],right_accumule_f[i+1],self.rerooting_upper_dp[x]])) if self.subtree: self.rerooting_parents=parents def Rerooting(self,root,subtree=None): assert self.subtree or subtree==None if self.subtree and root!=subtree: if self.rerooting_depth[subtree]>=self.rerooting_depth[root]: x=self.rerooting_parents[subtree] else: x=self.rerooting_PD.Permutation_Doubling(root,self.rerooting_depth[root]-self.rerooting_depth[subtree]-1) if self.rerooting_parents[x]!=subtree: x=self.rerooting_parents[subtree] if self.rerooting_parents[subtree]==x: retu=self.rerooting_f(subtree,self.rerooting_lower_dp[subtree]) else: retu=self.rerooting_upper_dp[x] else: if root==self.rerooting_s: retu=self.rerooting_f(root,self.rerooting_lower_dp[root]) else: retu=self.rerooting_f(root,self.rerooting_f_merge(root,[self.rerooting_lower_dp[root],self.rerooting_upper_dp[root]])) return retu def Build_Approach(self,s): self.approach_parents,self.approach_depth=self.SIV_DFS(s,parents=True,unweighted_dist=True) self.approach_parents[s]=s self.approach_PD=Path_Doubling(self.V,self.approach_parents) self.approach_PD.Build_Next() def Approach(self,x,y): if x==y: return None if self.approach_depth[x]>=self.approach_depth[y]: return self.approach_parents[x] retu=self.approach_PD.Permutation_Doubling(y,self.approach_depth[y]-self.approach_depth[x]-1) if self.approach_parents[retu]==x: return retu else: return self.approach_parents[x] def Build_Auxiliary_Tree(self,s): self.Build_LCA(s,segment_tree=True) self.auxiliary_tree_use=[False]*self.V def Auxiliary_Tree(self,points): points=sorted(list(set(points)),key=lambda x:self.lca_dfs_in_index[x]) for x in points: self.auxiliary_tree_use[x]=True le=len(points) for i in range(le-1): lca=self.LCA(points[i],points[i+1]) if not self.auxiliary_tree_use[lca]: points.append(lca) self.auxiliary_tree_use[lca]=True points.sort(key=lambda x:self.lca_dfs_in_index[x]) le=len(points) parents=[None]*le stack=[] for i in range(le): while stack and self.lca_dfs_out_index[points[stack[-1]]]<self.lca_dfs_in_index[points[i]]: stack.pop() if stack: parents[i]=stack[-1] stack.append(i) for x in points: self.auxiliary_tree_use[x]=False return parents,points def Centroid(self,root=0): x=root parents,size=self.SIV_DFS(x,parents=True,subtree_size=True) while True: for y in self.graph[x]: if self.weighted: y,d=y if y==parents[x]: continue if size[y]*2>size[root]: x=y break else: for y in self.graph[x]: if self.weighted: y,d=y if y==parents[x]: continue if size[root]<=2*size[y]: return x,y return x,None def Centroid_Decomposition(self,points=False,edges=False,tree=False,linked_point=False): if points: cd_points=[None]*self.V if edges: cd_edges=[None]*self.V if tree: cd_tree=[]*self.V if linked_point: cd_linked_point=[None]*self.V E=self.edges P=[i for i in range(self.V)] prev_centroid=None stack=[(E,P,None,prev_centroid)] if linked_point else [(E,P,prev_centroid)] while stack: if linked_point: E,P,lp,prev_centroid=stack.pop() else: E,P,prev_centroid=stack.pop() if len(P)==1: centroid=P[0] if edges: cd_edges[centroid]=[] if linked_point: cd_linked_point[centroid]=lp if points: cd_points[centroid]=[centroid] if tree and prev_centroid!=None: cd_tree.append((prev_centroid,centroid)) continue G=Graph(len(P),edges=E,weighted=self.weighted) centroid,_=G.Centroid() if tree and prev_centroid!=None: cd_tree.append((prev_centroid,P[centroid])) parents,tour=G.SIV_DFS(centroid,parents=True,preorder=True) dp=[None]*len(P) EE=[] PP=[] if linked_point: linked_points=[] for i,x in enumerate(G.graph[centroid]): if G.weighted: x,d=x dp[x]=(i,0) EE.append([]) PP.append([P[x]]) if linked_point: linked_points.append(P[x]) for x in tour[1:]: for y in G.graph[x]: if G.weighted: y,d=y if y==parents[x]: continue i,j=dp[x] jj=len(PP[i]) EE[i].append((j,jj,d) if G.weighted else (j,jj)) PP[i].append(P[y]) dp[y]=(i,jj) centroid=P[centroid] if points: cd_points[centroid]=P if edges: cd_edges[centroid]=E if linked_point: cd_linked_point[centroid]=lp if linked_point: for E,P,lp in zip(EE,PP,linked_points): stack.append((E,P,lp,centroid)) else: for E,P in zip(EE,PP): stack.append((E,P,centroid)) retu=() if points: retu+=(cd_points,) if edges: retu+=(cd_edges,) if tree: retu+=(cd_tree,) if linked_point: retu+=(cd_linked_point,) if len(retu)==1: retu=retu[0] return retu def Bridges(self): lowlink,preorder=self.MIV_DFS(lowlink=True,preorder=True) order=[None]*self.V for x in range(self.V): order[preorder[x]]=x bridges=[] for e in self.edges: if self.weighted: x,y,d=e else: x,y=e if order[x]<lowlink[y] or order[y]<lowlink[x]: bridges.append(e) return bridges def Articulation_Points(self): lowlink,parents,preorder=self.MIV_DFS(lowlink=True,parents=True,preorder=True) order=[None]*self.V for x in range(self.V): order[preorder[x]]=x articulation_points=[] for x in range(self.V): if parents[x]==None: if len({y for y in self.graph[x] if parents[y]==x})>=2: articulation_points.append(x) else: for y in self.graph[x]: if parents[y]!=x: continue if order[x]<=lowlink[y]: articulation_points.append(x) break return articulation_points def TECCD(self): lowlink,preorder=self.MIV_DFS(lowlink=True,preorder=True) order=[None]*self.V for x in range(self.V): order[preorder[x]]=x edges=[] for e in self.edges: if self.weighted: x,y,d=e else: x,y=e if order[x]>=lowlink[y] and order[y]>=lowlink[x]: edges.append((x,y)) teccd=Graph(self.V,edges=edges).MIV_DFS(linked_components=True) idx=[None]*self.V for i,lst in enumerate(teccd): for x in lst: idx[x]=i teccd_edges=[(idx[a],idx[b]) for a,b in self.edges if idx[a]!=idx[b]] return teccd,teccd_edges def LCD(self): lcd_points=self.MIV_DFS(linked_components=True) lcd_edges=[[] for i in range(len(lcd_points))] idx=[None]*self.V for i in range(len(lcd_points)): for j in range(len(lcd_points[i])): idx[lcd_points[i][j]]=(i,j) for tpl in self.edges: if self.weighted: x,y,d=tpl else: x,y=tpl i,j0=idx[x] i,j1=idx[y] if self.weighted: lcd_edges[i].append((j0,j1,d)) else: lcd_edges[i].append((j0,j1)) return lcd_points,lcd_edges def Dijkstra(self,s,route_restoration=False): dist=[self.inf]*self.V dist[s]=0 queue=[(0,s)] if route_restoration: parents=[None]*self.V while queue: dx,x=heapq.heappop(queue) if dist[x]<dx: continue for y,dy in self.graph[x]: if dist[y]>dx+dy: dist[y]=dx+dy if route_restoration: parents[y]=x heapq.heappush(queue,(dist[y],y)) if route_restoration: return dist,parents else: return dist def Bellman_Ford(self,s,route_restoration=False): dist=[self.inf]*self.V dist[s]=0 if route_restoration: parents=[None]*self.V for _ in range(self.V-1): for i,j,d in self.edges: if dist[j]>dist[i]+d: dist[j]=dist[i]+d if route_restoration: parents[j]=i if not self.directed and dist[i]>dist[j]+d: dist[i]=dist[j]+d if route_restoration: parents[i]=j negative_cycle=[] for i,j,d in self.edges: if dist[j]>dist[i]+d: negative_cycle.append(j) if not self.directed and dist[i]>dist[j]+d: negative_cycle.append(i) if negative_cycle: is_negative_cycle=[False]*self.V for i in negative_cycle: if is_negative_cycle[i]: continue else: queue=deque([i]) is_negative_cycle[i]=True while queue: x=queue.popleft() for y,d in self.graph[x]: if not is_negative_cycle[y]: queue.append(y) is_negative_cycle[y]=True if route_restoration: parents[y]=x for i in range(self.V): if is_negative_cycle[i]: dist[i]=-self.inf if route_restoration: return dist,parents else: return dist def Warshall_Floyd(self,route_restoration=False): dist=[[self.inf]*self.V for i in range(self.V)] for i in range(self.V): dist[i][i]=0 if route_restoration: parents=[[j for j in range(self.V)] for i in range(self.V)] for i,j,d in self.edges: if i==j: continue if dist[i][j]>d: dist[i][j]=d if route_restoration: parents[i][j]=i if not self.directed and dist[j][i]>d: dist[j][i]=d if route_restoration: parents[j][i]=j for k in range(self.V): for i in range(self.V): for j in range(self.V): if dist[i][j]>dist[i][k]+dist[k][j]: dist[i][j]=dist[i][k]+dist[k][j] if route_restoration: parents[i][j]=parents[k][j] for i in range(self.V): if dist[i][i]<0: for j in range(self.V): if dist[i][j]!=self.inf: dist[i][j]=-self.inf if route_restoration: for i in range(self.V): if dist[i][i]==0: parents[i][i]=None return dist,parents else: return dist def BFS_01(self,s,route_restoration=False): queue=deque([s]) seen=[False]*self.V dist=[self.inf]*self.V dist[s]=0 if route_restoration: parents=[None]*self.V while queue: x=queue.popleft() if seen[x]: continue seen[x]=False for y,d in self.graph[x]: if dist[y]>dist[x]+d: dist[y]=dist[x]+d if route_restoration: parents[y]=x if d: queue.append(y) else: queue.appendleft(y) if route_restoration: return dist,parents else: return dist def Distance_Frequency(self): mod=206158430209 cnt=[0]*self.V cd_points,cd_edges,cd_tree=self.Centroid_Decomposition(points=True,edges=True,tree=True) CD=Graph(self.V,edges=cd_tree) parents,tour=CD.SIV_DFS(cd_tree[0][0],parents=True,postorder=True) for x in tour: C=[0]*(len(cd_points[x])+1) for y in CD.graph[x]: if y==parents[x]: continue depth=Graph(len(cd_points[y]),edges=cd_edges[y],weighted=self.weighted).SIV_DFS(0,unweighted_dist=True) CC=[0]*(max(depth)+2) for d in depth: CC[d+1]+=1 cnt[d+1]+=2 C[d+1]+=1 poly=NTT_Pow(CC,2) for d,c in enumerate(poly): if d<self.V: cnt[d]-=c while C and C[-1]==0: C.pop() poly=NTT_Pow(C,2) for d,c in enumerate(poly): if d<self.V: cnt[d]+=c for i in range(self.V): cnt[i]//=2 return cnt def Shortest_Path_Count(self,s,dist,mod=0): cnt=[0]*self.V cnt[s]=1 for x in sorted([x for x in range(self.V)],key=lambda x:dist[x]): for y in self.graph[x]: if self.weighted: y,d=y else: d=1 if dist[x]+d==dist[y]: cnt[y]+=cnt[x] if mod: cnt[y]%=mod return cnt def K_Shortest_Path_Routing(self,s,t,K,edge_unicursal=False,point_unicursal=False): if point_unicursal: if self.weighted: dist,parents=self.Dijkstra(s,route_restoration=True) else: parents,dist=self.SIV_BFS(s,parents=True,unweighted_dist=True) route=tuple(self.Route_Restoration(s,t,parents)) queue=[(dist[t],route,[dist[x] for x in route])] set_queue=set() set_queue.add(route) retu=[] while queue and K: d,route,route_dist=heapq.heappop(queue) retu.append((d,route,route_dist)) K-=1 set_route=set() for i in range(len(route)-1): x=route[i] set_route.add(x) if self.weighted: edges=[(v,u,d) for u,v,d in self.edges if not u in set_route and not v in set_route] else: edges=[(v,u) for u,v in self.edges if not u in set_route and not v in set_route] G_rev=Graph(self.V,edges=edges,directed=self.directed,weighted=self.weighted,inf=self.inf) if self.weighted: dist_rev,parents_rev=G_rev.Dijkstra(t,route_restoration=True) else: parents_rev,dist_rev=G_rev.SIV_BFS(t,parents=True,unweighted_dist=True) for y in self.graph[x]: if self.weighted: y,d=y else: d=1 if y==route[i+1]: continue if dist_rev[y]==self.inf: continue tpl=route[:i+1]+tuple(self.Route_Restoration(t,y,parents_rev)[::-1]) if not tpl in set_queue: heapq.heappush(queue,(route_dist[i]+d+dist_rev[y],tpl,route_dist[:i+1]+[route_dist[i]+d+dist_rev[y]-dist_rev[z] for z in tpl[i+1:]])) set_queue.add(tpl) elif edge_unicursal: if self.weighted: dist,parents=self.Dijkstra(s,route_restoration=True) else: parents,dist=self.SIV_BFS(s,parents=True,unweighted_dist=True) route=tuple(self.Route_Restoration(s,t,parents)) queue=[(dist[t],route,[dist[x] for x in route])] set_queue=set() set_queue.add(route) retu=[] while queue and K: d,route,route_dist=heapq.heappop(queue) retu.append((d,route,route_dist)) K-=1 set_route=set() for i in range(len(route)-1): x=route[i] y=route[i+1] set_route.add((x,y,route_dist[i+1]-route_dist[i])) if not self.directed: set_route.add((y,x,route_dist[i+1]-route_dist[i])) if self.weighted: edges=[(v,u,d) for u,v,d in self.edges if not (u,v,d) in set_route] else: edges=[(v,u) for u,v in self.edges if not (u,v,d) in set_route] G_rev=Graph(self.V,edges=edges,directed=self.directed,weighted=self.weighted,inf=self.inf) if self.weighted: dist_rev,parents_rev=G_rev.Dijkstra(t,route_restoration=True) else: parents_rev,dist_rev=G_rev.SIV_BFS(t,parents=True,unweighted_dist=True) for y in self.graph[x]: if self.weighted: y,d=y else: d=1 if y==route[i+1]: continue if dist_rev[y]==self.inf: continue tpl=route[:i+1]+tuple(self.Route_Restoration(t,y,parents_rev)[::-1]) if not tpl in set_queue: heapq.heappush(queue,(route_dist[i]+d+dist_rev[y],tpl,route_dist[:i+1]+[route_dist[i]+d+dist_rev[y]-dist_rev[z] for z in tpl[i+1:]])) set_queue.add(tpl) else: if self.weighted: dist,parents=self.Dijkstra(s,route_restoration=True) else: parents,dist=self.SIV_BFS(s,parents=True,unweighted_dist=True) if dist[t]==self.inf: return False route_lst=[tuple(self.Route_Restoration(s,x,parents)) for x in range(self.V)] if self.weighted: edges_rev=[(j,i,d) for i,j,d in self.edges] else: edges_rev=[(j,i) for i,j in self.edges] G_rev=Graph(self.V,edges=edges_rev,weighted=self.weighted,directed=self.directed,inf=self.inf) if self.weighted: dist_rev,parents_rev=G_rev.Dijkstra(t,route_restoration=True) else: parents_rev,dist_rev=G_rev.SIV_BFS(t,parents=True,unweighted_dist=True) route_rev_lst=[] for x in range(self.V): route_rev_lst.append(tuple(self.Route_Restoration(t,x,parents_rev)[::-1])) route=route_lst[t] queue=[(dist[t],route,[dist[x] for x in route])] set_queue=set() set_queue.add(route) retu=[] while queue and K: d,route,route_dist=heapq.heappop(queue) retu.append((d,route,route_dist)) K-=1 for i in range(len(route)): x=route[i] for y in self.graph[x]: if self.weighted: y,d=y else: d=1 if i!=len(route)-1 and y==route[i+1]: continue tpl=route[:i+1]+route_rev_lst[y] if not tpl in set_queue: heapq.heappush(queue,(route_dist[i]+d+dist_rev[y],tpl,route_dist[:i+1]+[route_dist[i]+d+dist_rev[y]-dist_rev[z] for z in route_rev_lst[y]])) set_queue.add(tpl) return retu def Euler_Path(self,s=None,t=None): if self.directed: if not self.edges: return [] indegree=[0]*self.V outdegree=[0]*self.V graph=[[] for x in range(self.V)] for tpl in self.edges: if self.weighted: u,v,d=tpl else: u,v=tpl indegree[v]+=1 outdegree[u]+=1 graph[v].append(u) for x in range(self.V): if indegree[x]+1==outdegree[x]: if s==None: s=x elif s!=x: return None elif indegree[x]==outdegree[x]+1: if t==None: t=x elif t!=x: return None elif indegree[x]!=outdegree[x]: return None if (s,t)==(None,None): for x in range(self.V): if graph[x]: s=x t=x break elif s==None: s=t elif t==None: t=s elif s==t: for x in range(self.V): if indegree[x]!=outdegree[x]: return None queue=[t] euler_path=[] while queue: while graph[queue[-1]]: queue.append(graph[queue[-1]].pop()) x=queue.pop() euler_path.append(x) for x in range(self.V): if graph[x]: return None else: degree=[0]*self.V graph=[[] for x in range(self.V)] use_count=[defaultdict(int) for x in range(self.V)] for tpl in self.edges: if self.weighted: u,v,d=tpl else: u,v=tpl degree[v]+=1 degree[u]+=1 graph[u].append(v) graph[v].append(u) for x in range(self.V): if degree[x]%2: if s==None and t!=x: s=x elif t==None and s!=x: t=x elif not x in (s,t): return None if s==None and t==None: for x in range(self.V): if graph[x]: s=x t=x break else: s,t=0,0 elif s==None: s=t elif t==None: t=s elif s!=t: if degree[s]%2==0 or degree[t]%2==0: return None queue=[t] euler_path=[] while queue: while graph[queue[-1]]: if use_count[queue[-1]][graph[queue[-1]][-1]]: use_count[queue[-1]][graph[queue[-1]][-1]]-=1 graph[queue[-1]].pop() else: queue.append(graph[queue[-1]].pop()) use_count[queue[-1]][queue[-2]]+=1 x=queue.pop() euler_path.append(x) for x in range(self.V): if graph[x]: return None if euler_path[0]!=s: return None return euler_path def Route_Restoration(self,s,g,parents): route=[g] while s!=g: if parents[g]==None: route=[] break g=parents[g] route.append(g) route=route[::-1] return route def Negative_Cycls(self): dist=[0]*self.V for _ in range(self.V-1): for i,j,d in self.edges: dist[j]=min(dist[j],dist[i]+d) for i,j,d in self.edges: if dist[j]>dist[i]+d: return True return False def Kruskal(self,maximize=False,spanning_tree=False): UF=UnionFind(self.V) sorted_edges=sorted(self.edges if self.weighted else [(x,y,1) for x,y in self.edges],key=lambda tpl:tpl[2],reverse=maximize) if spanning_tree: st=[] else: cost=0 for x,y,d in sorted_edges: if not UF.Same(x,y): UF.Union(x,y) if spanning_tree: st.append((x,y,d)if self.weighted else (x,y)) else: cost+=d return st if spanning_tree else cost def Max_Clique(self): graph=[[False]*self.V for x in range(self.V)] for x in range(self.V): for y in self.graph[x]: if self.weighted: y,d=y graph[x][y]=True N0,N1=self.V//2,self.V-self.V//2 pop_count=[sum(bit>>i&1 for i in range(N1)) for bit in range(1<<N1)] is_clique0=[True]*(1<<N0) for j in range(N0): for i in range(j): if not graph[i][j]: is_clique0[1<<i|1<<j]=False for i in range(N0): for bit in range(1<<N0): if bit&1<<i: is_clique0[bit]=is_clique0[bit]&is_clique0[bit^1<<i] is_clique1=[True]*(1<<N1) for j in range(N1): for i in range(j): if not graph[i+N0][j+N0]: is_clique1[1<<i|1<<j]=False for i in range(N1): for bit in range(1<<N1): if bit&1<<i: is_clique1[bit]=is_clique1[bit]&is_clique1[bit^1<<i] max_clique_bit=[bit if is_clique0[bit] else 0 for bit in range(1<<N0)] for i in range(N0): for bit in range(1<<N0): if bit&1<<i and pop_count[max_clique_bit[bit]]<pop_count[max_clique_bit[bit^1<<i]]: max_clique_bit[bit]=max_clique_bit[bit^1<<i] dp=[(1<<N0)-1]*(1<<N1) for j in range(N1): for i in range(N0): if not graph[j+N0][i]: dp[1<<j]^=1<<i for i in range(N1): for bit in range(1<<N1): if bit&1<<i: dp[bit]&=dp[bit^1<<i] bit0,bit1=0,0 for bit in range(1<<N1): if is_clique1[bit] and pop_count[max_clique_bit[dp[bit]]]+pop_count[bit]>pop_count[bit0]+pop_count[bit1]: bit0=max_clique_bit[dp[bit]] bit1=bit max_clique=[i for i in range(N0) if bit0&1<<i]+[i+N0 for i in range(N1) if bit1&1<<i] return max_clique def Cliques(self): graph=[[False]*self.V for x in range(self.V)] for x in range(self.V): for y in self.graph[x]: if self.weighted: y,d=y graph[x][y]=True cliques=[] points=[x for x in range(self.V)] while points: l=len(points) min_degree,min_degree_point=self.inf,None sum_degree=0 for x in points: s=sum(graph[x][y] for y in points) sum_degree+=s if s<min_degree: min_degree=s min_degree_point=x if min_degree**2>=sum_degree: lst=points else: lst=[x for x in points if x==min_degree_point or graph[min_degree_point][x]] l=len(lst) is_clique=[True]*(1<<l) for j in range(l): for i in range(j): if not graph[lst[i]][lst[j]]: is_clique[1<<i|1<<j]=False for i in range(l): for bit in range(1<<l): if bit&1<<i: is_clique[bit]=is_clique[bit]&is_clique[bit^1<<i] if min_degree**2>=sum_degree: for bit in range(1<<l): if is_clique[bit]: cliques.append([lst[i] for i in range(l) if bit&1<<i]) else: idx=lst.index(min_degree_point) for bit in range(1<<l): if is_clique[bit] and bit&1<<idx: cliques.append([lst[i] for i in range(l) if bit&1<<i]) if min_degree**2>=sum_degree: points=[] else: points=[x for x in points if x!=min_degree_point] return cliques def Coloring_Count(self,mod=0): is_independent_set=[True]*(1<<self.V) for x in range(self.V): for y in self.graph[x]: is_independent_set[1<<x|1<<y]=False for x in range(self.V): for bit in range(1<<self.V): if bit&1<<x: is_independent_set[bit]&=is_independent_set[bit^1<<x] independent_set_count=[int(bl) for bl in is_independent_set] for x in range(self.V): for bit in range(1<<self.V): if bit&1<<x: independent_set_count[bit]+=independent_set_count[bit^1<<x] sign=[None]*(1<<self.V) sign[0]=-1 if self.V%2 else 1 for bit in range(1,1<<self.V): sign[bit]=-sign[bit^(bit&-bit)] coloring_count=[0]*(self.V+1) for bit in range(1<<self.V): pow_cnt=1 for k in range(self.V+1): if mod: coloring_count[k]+=pow_cnt*sign[bit]%mod coloring_count[k]%=mod else: coloring_count[k]+=pow(independent_set_count[bit],k)*sign[bit] pow_cnt*=independent_set_count[bit] if mod: pow_cnt%=mod return coloring_count def Chromatic_Number(self): coloring_count=self.Coloring_Count(mod=(1<<61)-1) for chromatic_number in range(self.V+1): if coloring_count[chromatic_number]: break return chromatic_number def Ford_Fulkerson(self,s,t): max_flow=0 residual_graph=[defaultdict(int) for i in range(self.V)] if self.weighted: for i,j,d in self.edges: if not d: continue residual_graph[i][j]+=d if not self.directed: residual_graph[j][i]+=d else: for i,j in self.edges: residual_graph[i][j]+=1 if not self.directed: residual_graph[j][i]+=1 while True: parents=[None]*self.V parents[s]=s seen=[False]*self.V seen[s]=True queue=deque([s]) while queue: x=queue.popleft() for y in residual_graph[x].keys(): if not seen[y]: seen[y]=True queue.append(y) parents[y]=x if y==t: tt=t while tt!=s: residual_graph[parents[tt]][tt]-=1 residual_graph[tt][parents[tt]]+=1 if not residual_graph[parents[tt]][tt]: residual_graph[parents[tt]].pop(tt) tt=parents[tt] max_flow+=1 break else: continue break else: break return max_flow def BFS(self,s): seen=[False]*self.V seen[s]=True queue=deque([s]) while queue: x=queue.popleft() for y in self.graph[x]: if self.weighted: y,d=y if not seen[y]: seen[y]=True queue.append(y) return def DFS(self,s): seen=[False]*self.V finished=[False]*self.V stack=[(s,0)] if self.weighted else [s] while stack: if self.weighted: x,d=stack.pop() else: x=stack.pop() if not seen[x]: seen[x]=True stack.append((x,d) if self.weighted else x) for y in self.graph[x]: if self.weighted: y,d=y if not seen[y]: stack.append((y,d) if self.weighted else y) elif not finished[x]: finished[x]=True return import bisect N=int(input()) edges=[] for i in range(N-1): a,b=map(int,input().split()) a-=1;b-=1 edges.append((a,b)) G=Graph(N,edges=edges) S=list(map(int,list(input()))) for i in range(N): S[i]*=2 S[i]-=1 P,E=G.Centroid_Decomposition(points=True,edges=True) ans=0 for i in range(N): g=P[i].index(i) le=len(P[i]) GG=Graph(le,E[i]) parents,tour=GG.SIV_DFS(g,parents=True,preorder=True) dp_C=[0]*le dp_P=[None]*le for x in tour: for y in GG.graph[x]: if y==parents[x]: continue dp_C[y]=dp_C[x]+S[P[i][y]] if dp_P[x]==None: dp_P[y]=y else: dp_P[y]=dp_P[x] C=[] dct_C=defaultdict(list) for x in range(le): if x==g: continue C.append(dp_C[x]) dct_C[dp_P[x]].append(dp_C[x]) def calc_cnt(C,s): C.sort() retu=0 for j in range(len(C)): c=C[j] retu+=len(C)-max(j+1,bisect.bisect_right(C,-c-s)) return retu ans+=calc_cnt(C,S[P[i][g]]) for CC in dct_C.values(): ans-=calc_cnt(CC,S[P[i][g]]) for c in C: if c+S[P[i][g]]>0: ans+=1 if S[P[i][g]]>0: ans+=1 print(ans)