結果

問題 No.1054 Union add query
コンテスト
ユーザー 👑 SPD_9X2
提出日時 2025-07-17 00:05:27
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,827 ms / 2,000 ms
コード長 2,606 bytes
コンパイル時間 430 ms
コンパイル使用メモリ 82,344 KB
実行使用メモリ 223,220 KB
最終ジャッジ日時 2025-07-17 00:05:40
合計ジャッジ時間 12,177 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 8
権限があれば一括ダウンロードができます

ソースコード

diff # 

"""

https://yukicoder.me/problems/no/1054

mergeするときに、親頂点を追加
各頂点に、(今判明している最高の頂点、その頂点を除くパス上の重み和)
を管理

"""

import sys
from sys import stdin

class DSU():

    def __init__(self, n:int):

        self.n = n
        self.p = [i for i in range(n)]
        self.rank = [i for i in range(n)]
        self.sizelis = [1] * n

    def leader(self,a):
        stk = []
        while self.p[a] != a:
            stk.append(a)
            a = self.p[a]
        for v in stk:
            self.p[v] = a
        return a

    def merge(self, a, b):
        ap = self.leader(a)
        bp = self.leader(b)
        if ap == bp:
            return ap

        if self.rank[ap] > self.rank[bp]:
            self.p[bp] = ap
            self.sizelis[ap] += self.sizelis[bp]
        elif self.rank[ap] < self.rank[bp]:
            self.p[ap] = bp
            self.sizelis[bp] += self.sizelis[ap]
        else:
            self.p[bp] = ap
            self.sizelis[ap] += self.sizelis[bp]
            self.rank[ap] += 1
        return self.p[ap]

    def same(self,a,b):
        return self.leader(a) == self.leader(b)

    def size(self,a):
        return self.sizelis[ self.leader(a) ]

    def groups(self):
        dic = {}
        for v in range(self.n):
            vp = self.leader(v)
            if vp not in dic:
                dic[vp] = [v]
            else:
                dic[vp].append(v)
        return list(dic.values())


N,Q = map(int,stdin.readline().split())

uf = DSU(N)
lis = [ [None,0] for i in range(N) ]

# 頂点vから、親と、そこまでのコストを求める
def search(v):

    vs = [ v ]
    while lis[v][0] != None:
        v = lis[v][0]
        vs.append(v)

    # 縮約する
    costs = []
    cost = 0
    for i,v in enumerate(list(reversed(vs))):
        if i != 0:
            cost += lis[v][1]
        costs.append(cost)
    costs.reverse()

    for v,c in zip(vs[:-1],costs[:-1]):
        lis[v] = [ vs[-1] , c ]

    return vs[-1] , cost + lis[vs[-1]][1]

ANS = []
for qidx in range(Q):

    T,A,B = map(int,stdin.readline().split())

    if T == 1:
        A -= 1
        B -= 1
        if not uf.same(A,B):
            uf.merge(A,B)
            pa,_ = search(A)
            pb,_ = search(B)

            vidx = len(lis)
            lis[pa][0] = vidx
            lis[pb][0] = vidx
            lis.append( [None,0] )
    
    elif T == 2:
        A -= 1
        pa,_ = search(A)
        lis[pa][1] += B

    else:
        A -= 1
        ANS.append(search(A)[1])

print (*ANS,sep="\n")
0