class Tree: 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): return self.index<=x>=1 i+=1 return x def lowest_common_ancestor(self,x,y): """頂点x,yの最小共通先祖(x,yに共通する先祖で最も深いもの)を求める. """ assert self.__after_seal_check(x,y) dd=self.vertex_depth(y)-self.vertex_depth(x) if dd<0: x,y=y,x dd=-dd y=self.upper(y,dd) if x==self.root: return x if x==y: return x d=self.vertex_depth(x) b=d.bit_length() X=self.upper_list for k in range(b-1,-1,-1): px=X[k][x];py=X[k][y] if px!=py: x=px;y=py return self.upper(x,1) def __degree_count(self): assert self.__after_seal_check() if hasattr(self,"deg"): return self.deg=[0]*(self.index+self.N) for v in range(self.index,self.index+self.N): d=len(self.children[v])+1 if d!=self.root: d-=1 self.deg[v]=d return def degree(self,v): """頂点vの次数を求める. """ assert self.__after_seal_check(v) if not hasattr(self,"deg"): self.__degree_count() return self.deg[v] def diameter(self): """木の直径を求める. """ assert self.__after_seal_check() from collections import deque def bfs(start): X=[-1]*(self.index+self.N) Q=deque([start]) X[start]=0 pa=self.parent ch=self.children while Q: x=Q.popleft() if 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 y,z,d def path(self,u,v): """頂点u,v間のパスを求める. """ assert self.__after_seal_check(u,v) w=self.lowest_common_ancestor(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_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 is_leaf(self,v): """頂点vは葉? """ return not bool(self.children[v]) def distance(self,u,v): """2頂点u,v間の距離を求める. """ assert self.__after_seal_check(u,v) dep=self.vertex_depth return dep(u)+dep(v)-2*dep(self.lowest_common_ancestor(u,v)) def __descendant_count(self): assert self.__after_seal_check() if hasattr(self,"des_count"): return if not hasattr(self,"tower"): self.depth_search(False) self.des_count=[1]*(self.index+self.N) pa=self.parent for T in self.tower[:0:-1]: for x in T: self.des_count[pa[x]]+=self.des_count[x] return def descendant_count(self,v): """頂点vの子孫の数を求める. """ assert self.__after_seal_check(v) self.__descendant_count() return self.des_count[v] def subtree_size(self,v): """頂点vを根とした部分根付き木のサイズを求める. """ return self.descendant_count(v) def preorder(self,v): """頂点vの行きがけ順を求める. """ assert self.__after_seal_check(v) if hasattr(self,"preorder_number"): self.preorder_number[v] from collections import deque Q=deque([self.root]) T=[-1]*(self.N+self.index) p=1 while Q: x=Q.popleft() T[x]=p p+=1 C=self.children[x] for y in C: Q.append(y) self.preorder_number=T return T[v] def dfs_yielder(self): """DFSにおける頂点の出入りをyieldする. (v,1): 頂点vに入る (v,0): 頂点vを出る """ assert self.__after_seal_check() #最初 yield (self.root,1) v=self.root ch=self.children 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) while True: if R[v]==S[v]: #もし,進めないならば yield (v,0) #頂点vを出る if v==self.root: break else: v=pa[v] else: #進める w=v v=ch[v][S[v]] S[w]+=1 yield (v,1) def top_down(self): assert self.__after_seal_check() if not hasattr(self,"tower"): self.depth_search(False) for E in self.tower: for v in E: yield v def bottom_up(self): assert self.__after_seal_check() if not hasattr(self,"tower"): self.depth_search(False) for E in self.tower[::-1]: for v in E: yield v def tree_dp(self,calc,unit,f,g,Mode=False): """葉から木DPを行う. [input] calc:モノイドを成す2項演算 M x M -> M unit:Mの単位元 f,g: M -> M Mode: False->根の値のみ, True->全ての値 [補足] 頂点 v の子が x,y,z,...のとき, 更新式は dp[v]=g(f(x)*f(y)*f(z)*...) になる. """ data=[unit]*(self.index+self.N) pa=self.parent for x in self.bottom_up(): if x==self.root: break data[x]=g(data[x]) data[pa[x]]=calc(data[pa[x]],f(data[x])) if Mode: return data else: return data[self.root] def euler_tour(self): """ オイラーツアーに関する計算を行う. """ assert self.__after_seal_check() #最初 X=[]; X_append=X.append #X: Euler Tour のリスト v=self.root ch=self.children 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) while True: X_append(v) if R[v]==S[v]: #もし,進めないならば if v==self.root: break else: v=pa[v] else: #進める w=v v=ch[v][S[v]] S[w]+=1 self.euler=X self.in_time=[-1]*(self.index+self.N) self.out_time=[-1]*(self.index+self.N) for i in range(len(X)): v=X[i] if self.in_time[v]==-1: self.in_time[v]=self.out_time[v]=i else: self.out_time[v]=i #================================================= def Making_Tree(N,E,root,index=0): """木を作る. N:頂点数 E:辺のリスト root:根 """ from collections import deque F=[[] for _ in range(index+N)] for u,v in E: assert index<=uX[i][W]: v,w=List[i] L.append((i,List[i])) W-=w return alpha,L[::-1] else: X=[0]*(Weight+1) for v,w in List: for s in range(Weight,w-1,-1): X[s]=max(X[s],X[s-w]+v) return max(X) #================================================== N,K=map(int,input().split()) E=[]; F={} for _ in range(N-1): a,b,c=map(int,input().split()) if a>b: a,b=b,a E.append((a,b)) F[(a,b)]=c root=1 T=Making_Tree(N,E,1,1) Under_Leaf=[0]*(N+1) ch=T.children for v in T.bottom_up(): if T.is_leaf(v): Under_Leaf[v]=1 else: for w in ch[v]: Under_Leaf[v]+=Under_Leaf[w] Base=0 X=[] T.depth_search(False) dep=T.depth for u,v in F: if dep[u]