結果

問題 No.3309 Aging Railway
コンテスト
ユーザー tkykwtnb
提出日時 2025-10-24 23:14:53
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,275 bytes
コンパイル時間 155 ms
コンパイル使用メモリ 82,464 KB
実行使用メモリ 264,552 KB
最終ジャッジ日時 2025-10-24 23:15:04
合計ジャッジ時間 5,270 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 3 TLE * 1 -- * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import defaultdict
class UnionFind:
    def __init__(self,n):
        self._n=n
        self._parent_size=[-1 for _ in range(n)]
    def leader(self,a):
        if self._parent_size[a]<0:return a
        self._parent_size[a]=self.leader(self._parent_size[a])
        return self._parent_size[a]
    def merge(self,a,b):
        x,y=self.leader(a),self.leader(b)
        if x==y: return
        if abs(self._parent_size[x])<abs(self._parent_size[y]):x,y=y,x
        self._parent_size[x]+=self._parent_size[y]
        self._parent_size[y]=x
        return
N,M=map(int,input().split())
UV=[]
for _ in range(N-1):
    u,v=map(int,input().split())
    u-=1;v-=1
    UV.append((u,v))
IS=[]
IT=[]
SI=defaultdict(set)
TI=defaultdict(set)
for i in range(M):
    s,t=map(int,input().split())
    s-=1;t-=1
    IS.append(s)
    IT.append(t)
    SI[s].add(i)
    TI[t].add(i)
uf=UnionFind(N)
ans=[set()]
rest=set(list(range(M)))
for u,v in UV[::-1]:
    uf.merge(u,v)
    # 駅uと駅vが繋がったとき、駅uの利用者iの目的駅wが同じグループなら通勤可能
    user=set()
    for i in rest:
        if uf.leader(IS[i])==uf.leader(IT[i]):user.add(i)
    ans.append(ans[-1]|user)
    rest-=ans[-1]
for a in list(reversed(ans))[1:]:
    print(len(a))
0