結果
問題 |
No.3206 う し た ウ ニ 木 あ く ん 笑
|
ユーザー |
![]() |
提出日時 | 2025-07-22 00:36:31 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 726 ms / 3,000 ms |
コード長 | 2,681 bytes |
コンパイル時間 | 437 ms |
コンパイル使用メモリ | 83,024 KB |
実行使用メモリ | 134,064 KB |
最終ジャッジ日時 | 2025-07-22 00:36:44 |
合計ジャッジ時間 | 11,797 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 30 |
ソースコード
import sys input = sys.stdin.readline from collections import Counter from operator import itemgetter n=int(input()) E=[[] for i in range(n)] for i in range(n-1): x,y=map(int,input().split()) x-=1 y-=1 E[x].append(y) E[y].append(x) ROOT=0 QUE=[ROOT] Parent=[-1]*n Parent[ROOT]=n # ROOTの親を定めておく. Child=[[] for i in range(n)] TOP_SORT=[] # トポロジカルソート while QUE: # トポロジカルソートと同時に親を見つける x=QUE.pop() TOP_SORT.append(x) for to in E[x]: if Parent[to]==-1: Parent[to]=x Child[x].append(to) QUE.append(to) UP=[0]*n DOWN=[0]*n # xとParent[x]をつなぐedgeを考える # UP[x]は、xをROOTとする部分木に関する値。 # xとつながるnodeのうち、Parent[x]以外をxの子と捉える。 # DOWN[x]はParent[x]をROOTとする部分木に関する値。 # Parent[x]とつながるnodeのうち、x以外をParent[x]の子と捉える。 def compose_calc(x,y):# 子たちの値を合成する return max(x,y) unit=0 # 単位元 def final_ans(x,value):# 子たちから計算した値から答えを出す return 1+value for x in TOP_SORT[::-1]: if Child[x]==[]: UP[x]=unit continue k=unit # 子が全て1なら0、それ以外は1 for c in Child[x]: k=compose_calc(k,UP[c]) UP[x]=final_ans(x,k) COMPOSE=[unit]*n no_composed_value=-1 #composeされないときの値 # DOWN[x]を求めるときに使う # Parent[x]について、Parent[Parent[x]]以外からの寄与。 # 各iについて、for c in Child[i]についてUP[c]の値をみて、左右からの累積和を使って計算。 for i in range(n): X=[] for c in Child[i]: X.append(UP[c]) if X==[]: continue LEFT=[X[0]] for j in range(1,len(X)): LEFT.append(compose_calc(LEFT[-1],X[j])) RIGHT=no_composed_value for j in range(len(X)-1,-1,-1): if j!=0: COMPOSE[Child[i][j]]=compose_calc(LEFT[j-1],RIGHT) else: COMPOSE[Child[i][j]]=RIGHT RIGHT=compose_calc(RIGHT,X[j]) for x in TOP_SORT: if x==ROOT: DOWN[x]=0 continue p=Parent[x] if p==ROOT: k=COMPOSE[x] else: k=compose_calc(DOWN[p],COMPOSE[x]) DOWN[x]=final_ans(x,k) ANS=0 for i in range(n): LIST=[] for c in Child[i]: LIST.append(UP[c]+1) if 0<=Parent[i]<n: LIST.append(DOWN[i]+1) #print(LIST) LIST.sort(reverse=True) for i in range(len(LIST)): score=1+LIST[i]*(i+1) ANS=max(ANS,score) print(ANS)