結果

問題 No.1002 Twotone
ユーザー sasa8uyauya
提出日時 2025-02-28 02:53:50
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 866 bytes
コンパイル時間 465 ms
コンパイル使用メモリ 82,764 KB
実行使用メモリ 212,104 KB
最終ジャッジ日時 2025-02-28 02:54:52
合計ジャッジ時間 57,932 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 2
other WA * 17 TLE * 2 -- * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input=sys.stdin.buffer.readline

n,K=map(int,input().split())
e=[[] for i in range(n)]
for _ in range(n-1):
  a,b,c=map(int,input().split())
  a-=1
  b-=1
  c-=1
  e[a]+=[(b,c)]
  e[b]+=[(a,c)]

def CD(e):
  c=[]
  g=0
  p=[-1]*n
  v=[0]*n
  u=[0]*n
  sq=[(0,n)]
  for start,W in sq:
    g+=1
    q=[start]
    while len(q)>0:
      s=q[-1]
      if v[s]==0:
        v[s]=1
        for t,_ in e[s]:
          if v[t]==0 and p[t]==-1:
            q+=[t]
      else:
        u[s]=1+sum(u[t] for t,_ in e[s] if v[t]==0 and p[t]==-1)
        if all(W-u[t]>=u[t] if v[t]==0 else u[s]>=W-u[s] for t,_ in e[s] if p[t]==-1):
          nc=s
          if len(c)<g:
            p[nc]=len(c)
            c+=[nc]
            sq+=[(ns,u[ns]) if v[t]==0 else (ns,W-u[nc]) for ns,_ in e[nc] if p[ns]==-1]
        v[s]=0
        q.pop()
  return c,p

cdc,cdp=CD(e)

exit()
0