結果
問題 | No.1488 Max Score of the Tree |
ユーザー |
👑 ![]() |
提出日時 | 2021-05-21 02:19:53 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 108 ms / 2,000 ms |
コード長 | 14,052 bytes |
コンパイル時間 | 206 ms |
コンパイル使用メモリ | 82,536 KB |
実行使用メモリ | 67,400 KB |
最終ジャッジ日時 | 2024-10-10 07:26:07 |
合計ジャッジ時間 | 3,761 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 29 |
ソースコード
class Tree:def __init__(self,N,index=0):"""N頂点(index, index+1, ..., N-1+index)の根付き木を生成する."""self.N=Nself.index=indexself.parent=[-1]*(N+index)self.__mutable=Truedef vertex_exist(self,x):return self.index<=x<self.index+self.Ndef __after_seal_check(self,*vertexes):if self.__mutable:return Falsefor v in vertexes:if not self.vertex_exist(v):return Falsereturn Truedef is_mutable(self):return self.__mutable#設定パートdef root_set(self,root):"""頂点xを根に設定する."""assert self.vertex_exist(root)assert self.__mutableself.root=rootdef parent_set(self,x,y):"""頂点xの親をyに設定する."""assert self.vertex_exist(x)assert self.vertex_exist(y)assert self.__mutableself.parent[x]=ydef child_set(self,x,y):"""頂点xの子の一つにyを設定する."""assert self.vertex_exist(x)assert self.vertex_exist(y)assert self.__mutableself.parent[y]=xdef seal(self):"""木の情報を確定させる."""assert self.__mutableassert hasattr(self,"root")a=self.indexb=self.index+self.NC=[[] for _ in range(b)]p=self.parentve=self.vertex_existfor i in range(a,b):if i!=self.root:assert ve(p[i])C[p[i]].append(i)self.__mutable=Falseself.children=C#データを求める.def depth_search(self,Mode=True):"""木の深さを求める."""assert self.__after_seal_check()if hasattr(self,"depth"):return self.depthfrom collections import dequeC=self.childrenD=[-1]*(self.index+self.N)E=[[] for _ in range(self.N)]Q=deque([self.root])D[self.root]=0E[0]=[self.root]while Q:x=Q.popleft()d=D[x]for y in C[x]:D[y]=d+1E[d+1].append(y)Q.append(y)self.depth=Dself.tower=Eif Mode:return Ddef vertex_depth(self,x):"""頂点xの深さを求める."""assert self.__after_seal_check(x)if not hasattr(self,"depth"):self.depth_search(Mode=False)return self.depth[x]def __upper_list(self):assert self.__after_seal_check()if hasattr(self,"upper_list"):returnif not hasattr(self,"depth"):self.depth_search(False)b=max(self.depth).bit_length()X=[[-1]*(self.index+self.N) for _ in range(b)]Y=X[0]p=self.parentrg=range(self.index,self.index+self.N)for x in rg:if x!=self.root:Y[x]=p[x]else:Y[x]=self.rootfor k in range(1,b):Y=X[k-1]Z=X[k]for x in rg:Z[x]=Y[Y[x]]self.upper_list=Xdef upper(self,x,k,over=True):"""頂点xから見てk個親の頂点を求める.over:(頂点xの深さ)<kのときにTrueならば根を返し, Falseならばエラーを吐く."""assert self.__after_seal_check(x)assert 0<=kif not hasattr(self,"upper_list"):self.__upper_list()if self.vertex_depth(x)<k:if over:return self.rootelse:raise ValueErrori=0while k:if k&1:x=self.upper_list[i][x]k>>=1i+=1return xdef 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,xdd=-ddy=self.upper(y,dd)if x==self.root:return xif x==y:return xd=self.vertex_depth(x)b=d.bit_length()X=self.upper_listfor k in range(b-1,-1,-1):px=X[k][x];py=X[k][y]if px!=py:x=px;y=pyreturn self.upper(x,1)def __degree_count(self):assert self.__after_seal_check()if hasattr(self,"deg"):returnself.deg=[0]*(self.index+self.N)for v in range(self.index,self.index+self.N):d=len(self.children[v])+1if d!=self.root:d-=1self.deg[v]=dreturndef 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 dequedef bfs(start):X=[-1]*(self.index+self.N)Q=deque([start])X[start]=0pa=self.parentch=self.childrenwhile Q:x=Q.popleft()if X[pa[x]]==-1:Q.append(pa[x])X[pa[x]]=X[x]+1for y in ch[x]:if X[y]==-1:Q.append(y)X[y]=X[x]+1y=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,ddef path(self,u,v):"""頂点u,v間のパスを求める."""assert self.__after_seal_check(u,v)w=self.lowest_common_ancestor(u,v)pa=self.parentX=[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 Falsereturn 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 Falsev=self.upper(v,dd)return u==vdef 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_depthreturn 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"):returnif not hasattr(self,"tower"):self.depth_search(False)self.des_count=[1]*(self.index+self.N)pa=self.parentfor T in self.tower[:0:-1]:for x in T:self.des_count[pa[x]]+=self.des_count[x]returndef 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 dequeQ=deque([self.root])T=[-1]*(self.N+self.index)p=1while Q:x=Q.popleft()T[x]=pp+=1C=self.children[x]for y in C:Q.append(y)self.preorder_number=Treturn 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.rootch=self.childrenpa=self.parentR=[-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:breakelse:v=pa[v]else: #進めるw=vv=ch[v][S[v]]S[w]+=1yield (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 vdef 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 vdef tree_dp(self,calc,unit,f,g,Mode=False):"""葉から木DPを行う.[input]calc:モノイドを成す2項演算 M x M -> Munit:Mの単位元f,g: M -> MMode: False->根の値のみ, True->全ての値[補足]頂点 v の子が x,y,z,...のとき, 更新式はdp[v]=g(f(x)*f(y)*f(z)*...)になる."""data=[unit]*(self.index+self.N)pa=self.parentfor x in self.bottom_up():if x==self.root:breakdata[x]=g(data[x])data[pa[x]]=calc(data[pa[x]],f(data[x]))if Mode:return dataelse:return data[self.root]def euler_tour(self):""" オイラーツアーに関する計算を行う."""assert self.__after_seal_check()#最初X=[]; X_append=X.append #X: Euler Tour のリストv=self.rootch=self.childrenpa=self.parentR=[-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:breakelse:v=pa[v]else: #進めるw=vv=ch[v][S[v]]S[w]+=1self.euler=Xself.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]=ielse:self.out_time[v]=i#=================================================def Making_Tree(N,E,root,index=0):"""木を作る.N:頂点数E:辺のリストroot:根"""from collections import dequeF=[[] for _ in range(index+N)]for u,v in E:assert index<=u<index+Nassert index<=v<index+Nassert u!=vF[u].append(v)F[v].append(u)X=[-1]*(index+N)X[root]=rootC=[[] for _ in range(index+N)]Q=deque([root])while Q:x=Q.popleft()for y in F[x]:if X[y]==-1:X[y]=xQ.append(y)C[x].append(y)T=Tree(N,index)T.root_set(root)T.parent=XT.children=CT.seal()return Tdef Knapsack_01_Weight(List,Weight,Mode=False):"""重さが非常に軽い01-Knapsack Problemを解く.List:各要素はタプル(v,w) の形で, vは価値, wは重さMode:Mode=Trueのとき, 最大値とそれを達成する例を返す.[計算量]O(NW)"""if Mode:X=[[0]*(Weight+1) for _ in range(len(List)+1)]for i,(v,w) in enumerate(List,0):E=X[i]F=X[i+1]for s in range(Weight,w-1,-1):F[s]=max(E[s],E[s-w]+v)alpha=max(X[-1])W=X[-1].index(alpha)L=[]for i in range(len(List)-1,-1,-1):if X[i+1][W]>X[i][W]:v,w=List[i]L.append((i,List[i]))W-=wreturn 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,aE.append((a,b))F[(a,b)]=croot=1T=Making_Tree(N,E,1,1)Under_Leaf=[0]*(N+1)ch=T.childrenfor v in T.bottom_up():if T.is_leaf(v):Under_Leaf[v]=1else:for w in ch[v]:Under_Leaf[v]+=Under_Leaf[w]Base=0X=[]T.depth_search(False)dep=T.depthfor u,v in F:if dep[u]<dep[v]: w=velse: w=ua=min(u,v)b=max(u,v)Base+=F[(a,b)]*Under_Leaf[w]X.append((F[(a,b)]*Under_Leaf[w],F[(a,b)]))print(Base+Knapsack_01_Weight(X,K,False))