結果
問題 | No.1103 Directed Length Sum |
ユーザー | 👑 Kazun |
提出日時 | 2021-03-05 18:00:30 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,450 ms / 3,000 ms |
コード長 | 10,463 bytes |
コンパイル時間 | 216 ms |
コンパイル使用メモリ | 82,268 KB |
実行使用メモリ | 336,884 KB |
最終ジャッジ日時 | 2024-10-06 19:03:22 |
合計ジャッジ時間 | 13,583 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 39 ms
55,812 KB |
testcase_01 | AC | 42 ms
56,052 KB |
testcase_02 | AC | 852 ms
336,884 KB |
testcase_03 | AC | 569 ms
283,424 KB |
testcase_04 | AC | 771 ms
181,096 KB |
testcase_05 | AC | 1,450 ms
260,336 KB |
testcase_06 | AC | 482 ms
145,644 KB |
testcase_07 | AC | 140 ms
91,136 KB |
testcase_08 | AC | 180 ms
98,532 KB |
testcase_09 | AC | 114 ms
85,664 KB |
testcase_10 | AC | 236 ms
110,240 KB |
testcase_11 | AC | 824 ms
192,512 KB |
testcase_12 | AC | 471 ms
146,188 KB |
testcase_13 | AC | 239 ms
111,232 KB |
testcase_14 | AC | 102 ms
83,616 KB |
testcase_15 | AC | 350 ms
129,148 KB |
testcase_16 | AC | 961 ms
204,716 KB |
testcase_17 | AC | 991 ms
210,052 KB |
testcase_18 | AC | 249 ms
110,188 KB |
testcase_19 | AC | 891 ms
196,176 KB |
testcase_20 | AC | 112 ms
83,848 KB |
testcase_21 | AC | 167 ms
97,748 KB |
testcase_22 | AC | 672 ms
172,852 KB |
testcase_23 | AC | 389 ms
136,620 KB |
ソースコード
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<self.index+self.N def __after_seal_check(self,*vertexes): if self.__mutable: return False for v in vertexes: if not self.vertex_exist(v): return False return True def is_mutable(self): return self.__mutable #設定パート def root_set(self,root): """頂点xを根に設定する. """ assert self.vertex_exist(root) assert self.__mutable self.root=root def parent_set(self,x,y): """頂点xの親をyに設定する. """ assert self.vertex_exist(x) assert self.vertex_exist(y) assert self.__mutable self.parent[x]=y def child_set(self,x,y): """頂点xの子の一つにyを設定する. """ assert self.vertex_exist(x) assert self.vertex_exist(y) assert self.__mutable self.parent[y]=x def seal(self): """木の情報を確定させる. """ assert self.__mutable assert hasattr(self,"root") a=self.index b=self.index+self.N C=[[] for _ in range(b)] p=self.parent ve=self.vertex_exist for i in range(a,b): if i!=self.root: assert ve(p[i]) C[p[i]].append(i) self.__mutable=False self.children=C #データを求める. def depth_search(self,Mode=True): """木の深さを求める. """ assert self.__after_seal_check() if hasattr(self,"depth"): return self.depth from collections import deque C=self.children D=[-1]*(self.index+self.N) E=[[] for _ in range(self.N)] Q=deque([self.root]) D[self.root]=0 E[0]=[self.root] while Q: x=Q.popleft() d=D[x] for y in C[x]: D[y]=d+1 E[d+1].append(y) Q.append(y) self.depth=D self.tower=E if Mode: return D def 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"): return if 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.parent rg=range(self.index,self.index+self.N) for x in rg: if x!=self.root: Y[x]=p[x] else: Y[x]=self.root for k in range(1,b): Y=X[k-1] Z=X[k] for x in rg: Z[x]=Y[Y[x]] self.upper_list=X def upper(self,x,k,over=True): """頂点xから見てk個親の頂点を求める. over:(頂点xの深さ)<dのときにTrueならば根を返し, Falseならばエラーを吐く. """ assert self.__after_seal_check(x) assert 0<=k if not hasattr(self,"upper_list"): self.__upper_list() if self.vertex_depth(x)<k: if over: return self.root else: raise ValueError i=0 while k: if k&1: x=self.upper_list[i][x] k>>=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 #================================================ import sys input=sys.stdin.readline N=int(input()) T=Tree(N,1) F=[1]*(N+1);F[0]=0 Mod=10**9+7 for _ in range(N-1): a,b=map(int,input().split()) F[b]=0 T.child_set(a,b) root=F.index(1) T.root_set(root) T.seal() pa=T.parent D=[0]*(N+1) #長さの総和 E=[0]*(N+1) #道の本数 for x in T.bottom_up(): if x==root: continue y=pa[x] E[x]+=1 #自分から自分への道を加算 D[y]+=D[x]+E[x] E[y]+=E[x] D[y]%=Mod E[y]%=Mod print(sum(D)%Mod)