結果

問題 No.3405 Engineering University of Tree
コンテスト
ユーザー sasa8uyauya
提出日時 2025-12-29 12:31:34
言語 PyPy3
(7.3.17)
結果
TLE  
実行時間 -
コード長 1,629 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 295 ms
コンパイル使用メモリ 82,292 KB
実行使用メモリ 258,168 KB
最終ジャッジ日時 2025-12-29 12:32:13
合計ジャッジ時間 34,317 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 14 TLE * 7
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

n=int(input())
es=[[] for i in range(n-1)]
d=[0]*n
for i in range(n):
  q=list(map(int,input().split()))
  for j in q[1:]:
    es[j-1]+=[i]
  d[i]=q[0]
ne=[[] for i in range(n)]
for i,j in es:
  ne[min(d[i],d[j])]+=[(i,j)]
nv=[[] for i in range(n)]
for i in range(n):
  nv[d[i]]+=[i]

def solve(v,c,es,k):
  d={v:i for i,v in enumerate(v)}
  n=len(d)
  e=[[] for i in range(n)]
  for u,v in es:
    e[d[u]]+=[d[v]]
    e[d[v]]+=[d[u]]
  v=[0]*n
  u=[[0,0] for i in range(n)]
  a=0
  for i in range(n):
    if v[i]==0:
      q=[i]
      while len(q)>0:
        s=q[-1]
        if v[s]==0:
          v[s]=1
          for t in e[s]:
            if v[t]:
              e[s].remove(t)
              break
          q+=e[s]
        else:
          u[s][0]=sum(max(u[t]) for t in e[s])
          if c[s]-1>=k and s!=i:
            nu=1
            nu+=sum(max(u[t]) for t in e[s])
            nu-=sum(sorted(max(u[t])-u[t][0] for t in e[s])[:max(k-(c[s]-1-len(e[s])),0)])
            u[s][0]=max(u[s][0],nu)
          if c[s]>=k and s!=i:
            nu=1
            nu+=sum(max(u[t]) for t in e[s])
            nu-=sum(sorted(max(u[t])-u[t][0] for t in e[s])[:max(k-1-(c[s]-1-len(e[s])),0)])
            u[s][1]=max(u[s][1],nu)
          if c[s]>=k and s==i:
            nu=1
            nu+=sum(max(u[t]) for t in e[s])
            nu-=sum(sorted(max(u[t])-u[t][0] for t in e[s])[:max(k-(c[s]-len(e[s])),0)])
            u[s][0]=max(u[s][0],nu)
          q.pop()
      a+=u[i][0]
  return a

ans=[0]*n
es=[]
v=[]
c=[]
for k in reversed(range(1,n)):
  es+=ne[k]
  v+=nv[k]
  c+=[k]*len(nv[k])
  ans[k]=solve(v,c,es,k)

print(*ans[1:])
0