class Tree: __slots__=("N", "index", "parent", "__mutable", "root", "children", "depth", "tower", "upper_list", "des_count", "preorder_number", "euler_vertex", "euler_edge", "in_time", "out_time", "lca_dst", "hld_hedge") def __init__(self, N, index=0): """ N 頂点 (index, index+1, ..., N-1+index) の根付き木を生成する. """ self.N=N self.index=index self.parent=[-1]*(N+index) self.__mutable=True def vertex_exist(self, x): """ 頂点 x が存在するかどうかを判定する. """ return self.index<=x>=1 i+=1 return x def lowest_common_ancestor_greedy(self, x, y): """頂点 x, y の最小共通先祖 (x,yに共通する先祖で最も深いもの) を "愚直に" 求める.""" assert self.__after_seal_check(x,y) dx=self.vertex_depth(x); dy=self.vertex_depth(y) if dxdy: x=pa[x] dx-=1 while x!=y: x=pa[x] y=pa[y] return x def __lca_prepare(self): assert self.__after_seal_check() N=self.N bit=max(1, ((2*N-1)-1).bit_length()) D=[[0]*(2*N-1) for _ in range(bit)] self.euler_tour_vertex() tour=self.euler_vertex D[0]=tour.copy() dep=self.depth_search(True) for i in range(1, bit): shift=1<b: x,y=y,x a,b=b,a if a==b: return self.lca_dst[0][a] p=(a^b).bit_length()-1 tab=self.lca_dst[p] u=tab[a]; v=tab[b] return u if self.vertex_depth(u)= 0 and X[pa[x]]==-1: Q.append(pa[x]) X[pa[x]]=X[x]+1 for y in ch[x]: if X[y]==-1: Q.append(y) X[y]=X[x]+1 y=max(range(self.index,self.index+self.N), key=lambda x:X[x]) return y,X[y] y,_=bfs(self.root) z,d=bfs(y) return d,(y,z) def path(self, u, v, faster=False): """ 頂点 u, v 間のパスを求める. """ assert self.__after_seal_check(u,v) if faster: w=self.lowest_common_ancestor(u,v) else: w=self.lowest_common_ancestor_greedy(u,v) pa=self.parent X=[u] while u!=w: u=pa[u] X.append(u) Y=[v] while v!=w: v=pa[v] Y.append(v) return X+Y[-2::-1] def is_parent(self, u, v): """ u は v の親か? """ assert self.__after_seal_check(u,v) return v!=self.root and u==self.parent[v] def is_children(self, u, v): """ u は v の子か? """ assert self.__after_seal_check(u,v) return self.is_parent(v,u) def is_brother(self,u,v): """ 2つの頂点 u, v は兄弟 (親が同じ) か? """ assert self.__after_seal_check(u,v) if u==self.root or v==self.root: return False return self.parent[u]==self.parent[v] def is_ancestor(self,u,v): """ 頂点 u は頂点 v の先祖か? """ assert self.__after_seal_check(u,v) dd=self.vertex_depth(v)-self.vertex_depth(u) if dd<0: return False v=self.upper(v,dd) return u==v def is_descendant(self,u,v): """ 頂点 u は頂点 v の子孫か? """ assert self.__after_seal_check(u,v) return self.is_ancestor(v,u) def direction(self, u, v): """ 頂点 u から頂点 v (u!=v) へ向かうパスが頂点 u の次に通る頂点""" assert self.__after_seal_check(u,v) assert u!=v if self.is_ancestor(u,v): du=self.vertex_depth(u) dv=self.vertex_depth(v) return self.upper(v,dv-(du+1)) else: return self.parent[u] def jump(self, u, v, k, default=-1): """ 頂点 u から頂点 v へ向かうパスにおいて k 番目 (0-indexed) に通る頂点 (パスの長さが k より大きい場合は default) u: int v: int k: int default=-1: int """ assert self.__after_seal_check(u,v) if k==0: return u # lca を求める. x=u; y=v dx=self.vertex_depth(x); dy=self.vertex_depth(y) if dx>dy: x,y=y,x dx,dy=dy,dx y=self.upper(y, dy-dx) if x==self.root or x==y: w=x else: bit=dx.bit_length() X=self.upper_list for t in range(bit-1,-1,-1): px=X[t][x]; py=X[t][y] if px!=py: x=px; y=py w=self.parent[x] dist_uw=self.vertex_depth(u)-self.vertex_depth(w) dist_wv=self.vertex_depth(v)-self.vertex_depth(w) if dist_uw+dist_wv M unit: M の単位元 f: X x V x V → M: f(x,v,w): v が親, w が子 g: M x V → X: g(x,v) Mode: False → 根の値のみ, True → 全ての値 [補足] 頂点 v の子が x,y,z,..., w のとき, 更新式は * を merge として dp[v]=g(f(dp[x],v,x)*f(dp[y],v,y)*f(dp[z],v,z)*...*f(dp[w],v,w), v) になる. """ assert self.__after_seal_check() data=[unit]*(self.index+self.N) ch=self.children for x in self.bottom_up(): for y in ch[x]: data[x]=merge(data[x], f(data[y], x, y)) data[x]=g(data[x], x) if Mode: return data else: return data[self.root] def tree_dp_from_root(self, f, alpha): """ 根から木 DP を行う. [input] alpha: 初期値 f: X x V x V → X: f(x,v,w): v が親, w が子 [補足] 頂点 v の親が x のとき, 更新式は dp[v]=f(dp[x],x,v) (x!=root), alpha (x==root) になる. """ assert self.__after_seal_check() data=[0]*(self.index+self.N) ch=self.children data[self.root]=alpha for x in self.top_down(): for y in ch[x]: data[y]=f(data[x],x,y) return data def rerooting(self, merge, unit, f, g): """ 全方位木 DP を行う. [input] merge: 可換モノイドを成す2項演算 M x M -> M unit: M の単位元 f: X x V x V → M: f(x,v,w): v が親, w が子 g: M x V → X: g(x,v) ※ tree_dp_from_leaf と同じ形式 [補足] 頂点 v の子が x,y,z,..., w のとき, 更新式は * を merge として dp[v]=g(f(dp[x],v,x)*f(dp[y],v,y)*f(dp[z],v,z)*...*f(dp[w],v,w), v) になる. """ assert self.__after_seal_check() upper=[unit]*(self.index+self.N) lower=[unit]*(self.index+self.N) ch=self.children pa=self.parent #DFSパート lower=self.tree_dp_from_leaf(merge, unit, f, g, True) #BFSパート for v in self.top_down(): cc=ch[v] #累積マージ deg=len(cc) Left=[unit]; x=unit for c in cc: x=merge(x, f(lower[c], v, c)) Left.append(x) Right=[unit]; y=unit for c in cc[::-1]: y=merge(y, f(lower[c], v, c)) Right.append(y) Right=Right[::-1] for i in range(deg): c=cc[i] a=merge(Left[i], Right[i+1]) if v!=self.root: b=merge(a, f(upper[v], v, pa[v])) else: b=a upper[c]=g(b, v) A=[unit]*(self.index+self.N) for v in range(self.index,self.index+self.N): if v!=self.root: a=f(upper[v], v, pa[v]) else: a=unit for c in ch[v]: a=merge(a, f(lower[c], v, c)) A[v]=g(a, v) return A def euler_tour_vertex(self, order=None): """ オイラーツアー (vertex) に関する計算を行う. order: 頂点の順番を指定する (破壊的) """ assert self.__after_seal_check() if hasattr(self,"euler_vertex"): return #最初 X=[-1]*(2*self.N-1) #X: Euler Tour (vertex) のリスト v=self.root ch=self.children if order!=None: for i in range(self.index,self.index+self.N): ch[i].sort(key=order) pa=self.parent R=[-1]*self.index+[len(ch[x]) for x in range(self.index,self.index+self.N)] S=[0]*(self.index+self.N) for t in range(2*self.N-1): X[t]=v if R[v]==S[v]: v=pa[v] else: #進める w=v v=ch[v][S[v]] S[w]+=1 self.euler_vertex = X self.in_time = [-1] * (self.index + self.N) self.out_time = [-1] * (self.index + self.N) self.in_time[self.root] = 0 self.out_time[self.root] = 2 * self.N - 1 for t in range(1, 2 * self.N - 1): if self.is_parent(X[t - 1], X[t]): self.in_time[X[t]] = t else: self.out_time[X[t - 1]] = t def euler_tour_edge(self): """ オイラーツアー (edge) に関する計算を行う. (u, v, k): u から v へ向かう (k=+1 のときは葉へ進む向き, k=-1 のときは根へ進む向き) """ assert self.__after_seal_check() if hasattr(self,"euler_edge"): return if not hasattr(self, "euler_vertex"): self.euler_tour_vertex() self.euler_edge=[0]*(2*(self.N-1)) euler=self.euler_vertex pa=self.parent for t in range(2*(self.N-1)): u=euler[t]; v=euler[t+1] k=1 if u==pa[v] else -1 self.euler_edge[t]=(u,v,k) def centroid(self, all=False): """ 木の重心を求める all: False → 重心のうちの1頂点. True → 全ての重心. """ assert self.__after_seal_check() M=self.N//2 if not hasattr(self,"des_count"): self.__descendant_count() G=[]; ch=self.children; des=self.des_count for v in range(self.index, self.index+self.N): if self.N-des[v]>M: continue flag=1 for x in ch[v]: if des[x]>M: flag=0 break if flag: if all: G.append(v) else: return v return G def generated_subtree(self,S): """ S を含む最小の部分木の頂点を求める. """ assert self.__after_seal_check(*S) if not hasattr(self, "in_time"): self.euler_tour_vertex() S=sorted(set(S),key=lambda i:self.in_time[i]) K=len(S) T=set() for i in range(K-1): for a in self.path(S[i],S[i+1]): T.add(a) return sorted(T) def generated_subtree_size(self,S): """ S を含む最小の部分木のサイズを求める. """ assert self.__after_seal_check(*S) if not hasattr(self, "in_time"): self.euler_tour_vertex() S=sorted(set(S),key=lambda i:self.in_time[i]) K=len(S) X=0 for i in range(K-1): X+=self.distance(S[i],S[i+1]) return (X+self.distance(S[-1],S[0]))//2 #================================================= def Making_Tree_from_Adjacent_List(N, A, root, index=0): """ 隣接リストから木を作る.""" from collections import deque T=Tree(N, index) T.root_set(root) S=[False]*(N+index); S[root]=True Q=deque([root]) while Q: v=Q.popleft() for w in A[v]: if not S[w]: S[w]=True T.parent_set(w,v) Q.append(w) T.seal() return T def Making_Tree_from_Edges(N, E, root, index=0): """ 辺のリストから木を作る. N: 頂点数 E: 辺のリスト E=[(u[0],v[0]), ..., (u[N-2], v[N-2]) ] root: 根 """ from collections import deque A=[[] for _ in range(N+index)] for u,v in E: A[u].append(v) A[v].append(u) T=Tree(N, index) T.root_set(root) S=[False]*(N+index); S[root]=True Q=deque([root]) while Q: v=Q.popleft() for w in A[v]: if not S[w]: S[w]=True T.parent_set(w,v) Q.append(w) T.seal() return T def Spanning_Tree(N,E,root,index=0,exclude=False): """ 連結なグラフから全域木をつくる. N: 頂点数 E: 辺のリスト root: 根 exclude: 全域木から外れた辺のリストを出力するか. """ from collections import deque F=[set() for _ in range(index+N)] EE=[] L=[] for u,v in E: assert index<=u