結果

問題 No.3309 Aging Railway
コンテスト
ユーザー tkykwtnb
提出日時 2025-10-24 23:22:17
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,065 bytes
コンパイル時間 145 ms
コンパイル使用メモリ 82,712 KB
実行使用メモリ 426,796 KB
最終ジャッジ日時 2025-10-24 23:22:23
合計ジャッジ時間 5,171 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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)]
        """マイナスならリーダーであり値は要素数。プラスなら値は親の番号。"""
        self._members=[[i] for i 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
        self._members[x]+=self._members[y]
        return
    def same(self,a,b):
        return self.leader(a)==self.leader(b)
    def size(self,a):
        return abs(self._parent_size[self.leader(a)])
    def members(self,a):
        return self._members[self.leader(a)]
    def groups(self):
        _gruops=[]
        for i,s in enumerate(self._parent_size):
            if s<0:_gruops.append(tuple(self.members(i)))
        return _gruops
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()]
for u,v in UV[::-1]:
    uf.merge(u,v)
    # 駅uと駅vが繋がったとき、駅uの利用者iの目的駅wが同じグループなら通勤可能
    stations=set(uf.members(uf.leader(u)))
    cand=set()
    for s in stations:
        cand|=(SI[s])
        cand|=(TI[s])
    user=set()
    for i in (cand-ans[-1]):
        if uf.leader(IS[i])==uf.leader(IT[i]):user.add(i)
    ans.append(ans[-1]|user)
for a in list(reversed(ans))[1:]:
    print(len(a))
0