結果

問題 No.3309 Aging Railway
コンテスト
ユーザー tkykwtnb
提出日時 2025-10-24 22:49:03
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 2,201 bytes
コンパイル時間 446 ms
コンパイル使用メモリ 82,660 KB
実行使用メモリ 67,844 KB
最終ジャッジ日時 2025-10-24 22:49:07
合計ジャッジ時間 3,618 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other RE * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import defaultdict
from sortedcontainers import SortedList
class UnionFind:
    def __init__(self,n):
        self._n=n
        self._parent_size=[-1 for _ in range(n)]
        """マイナスならリーダーであり値は要素数。プラスなら値は親の番号。"""
        self._members=[SortedList([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が同じグループなら通勤可能
    user=set()
    for i in SI[u]:
        if uf.leader(u)==uf.leader(IT[i]):user.add(i)
    for i in SI[v]:
        if uf.leader(v)==uf.leader(IT[i]):user.add(i)
    for i in TI[u]:
        if uf.leader(u)==uf.leader(IS[i]):user.add(i)
    for i in TI[v]:
        if uf.leader(v)==uf.leader(IS[i]):user.add(i)
    ans.append(ans[-1]|user)
for a in list(reversed(ans))[1:]:
    print(len(a))
0