結果

問題 No.3405 Engineering University of Tree
コンテスト
ユーザー sasa8uyauya
提出日時 2025-12-29 10:30:37
言語 PyPy3
(7.3.17)
結果
WA  
実行時間 -
コード長 1,698 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 287 ms
コンパイル使用メモリ 82,784 KB
実行使用メモリ 264,584 KB
最終ジャッジ日時 2025-12-29 10:31:17
合計ジャッジ時間 37,374 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 2
other WA * 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):
  if k==1:
    print(v)
    print(c)
  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(u[t][0]-max(u[t]) 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(u[t][0]-max(u[t]) 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(u[t][0]-max(u[t]) 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]
      if k==1:
        print(u)
  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