結果
問題 | No.1418 Sum of Sum of Subtree Size |
ユーザー |
![]() |
提出日時 | 2021-03-05 22:05:39 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 349 ms / 2,000 ms |
コード長 | 2,353 bytes |
コンパイル時間 | 357 ms |
コンパイル使用メモリ | 81,792 KB |
実行使用メモリ | 105,952 KB |
最終ジャッジ日時 | 2024-10-07 02:02:05 |
合計ジャッジ時間 | 8,755 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 41 |
ソースコード
def rerooting(g,e_M):"""以下を書き換える"""def merge(x,y): #値 x に y をマージreturn (x[0]+y[0],x[1]+y[1])def h1(x,v): # x = dp[v][p] を親方向 v->p にマージする際の補正return (x[0]+1,x[1]+x[0]+2)#def h2(x,p,v): # x = dp[p][v] を子方向 p->v にマージする際の補正# 辺属性なら v が大事、頂点属性なら p が大事なことが多いdef h2(x,p,v): return h1(x,p)h_fin = lambda x:x"""dfs_bottom_up: 木DPdfs_top_down: rerooting"""def get_order(g):n = len(g)order = []st = [0]parent = [-1]*nwhile st:v = st.pop()order.append(v)for c in g[v]:if c != parent[v]:st.append(c)parent[c] = vreturn order, parentdef dfs_bottom_up(BU,hBU,parent,order):for i in order[::-1]:hBU[i] = h1(BU[i], i)if i: BU[parent[i]] = merge(BU[parent[i]], hBU[i])def dfs_top_down(hBU,hTD,g,parent,order):for v in order:acc_l = e_Mfor c in g[v]:if c==parent[v]:acc_l = merge(acc_l,hTD[v])else:hTD[c] = acc_lacc_l = merge(acc_l,hBU[c])acc_r = e_Mfor c in g[v][::-1]:if c==parent[v]:acc_r = merge(hTD[v],acc_r)else:hTD[c] = h2(merge(hTD[c],acc_r),parent[v],v)acc_r = merge(acc_r,hBU[c])order, parent = get_order(g)BU = [e_M]*nhBU = [e_M]*nhTD = [e_M]*ndfs_bottom_up(BU,hBU,parent,order)dfs_top_down(hBU,hTD,g,parent,order)for i in range(n):BU[i] = h_fin(merge(BU[i],hTD[i]))return BU######################################## https://atcoder.jp/contests/dp/submissions/17723902######################################## coding: utf-8# Your code here!import sysreadline = sys.stdin.readlineread = sys.stdin.readn = int(input())g = [[] for _ in range(n)]for _ in range(n-1):a,b = map(int,readline().split())g[a-1].append(b-1)g[b-1].append(a-1)ans = nfor i,j in rerooting(g,(0,0)):ans += jprint(ans)