class WeightedUnionFind: def __init__(self, n): self.n = n self.parents = [-1] * n self.weights = [0] * n def find(self, x): """ 根を見つける関数を定義(同時にxを直接根にくっつける操作も行う)""" tmp = [] parents = self.parents while parents[x] >= 0: tmp.append(x) x = parents[x] for y in reversed(tmp): self.weights[y] +=self.weights[self.parents[y]] parents[y] = x return x def union(self, x, y, weight): """連結する問題では、最初から順に連結すると連結し忘れが発生しがちなので、極力UnionFindを使う連結する問題では、最初から順に連結すると連結し忘れが発生しがちなので、極力UnionFindを使う連結する問題では、最初から順に連結すると連結し忘れが発生しがちなので、極力UnionFindを使う連結する問題では、最初から順に連結すると連結し忘れが発生しがちなので、極力UnionFindを使う 二つの木をくっつける(子を多く持つ方を根とした親子関係)。これは破壊的操作を行う。 向きは、 Xy-Xx=weight で定義されている """ x0 = self.find(x) y0 = self.find(y) weight += self.weights[x] - self.weights[y] if x0 == y0: return if self.parents[x0] > self.parents[y0]: x0, y0 = y0, x0 weight = -weight self.parents[x0] += self.parents[y0] self.parents[y0] = x0 self.weights[y0] = weight def diff(self, x, y): return self.weights[y]-self.weights[x] def same(self, x, y): """ xとyが同じ根の子かを判定 """ return self.find(x) == self.find(y) def size(self, x): """ xの根のparent(= 要素数)を返す """ return -self.parents[self.find(x)] def members(self, x): """ xが属するグループの要素をリストとして返す O(N)""" root = self.find(x) return [i for i in range(self.n) if self.find(i) == root] def roots(self): """ 全ての根の要素をリストとして返す O(N)""" return [i for i, x in enumerate(self.parents) if x < 0] def group_count(self): """ グループの数を返す O(1)""" return len(self.roots()) def size_list(self): """ 各グループの要素数のリストを返す(根の番号は返さない) O(N)""" return [-x for x in self.parents if x < 0] def all_group_members(self): """ {根:[根の子(根を含む)のリスト],...}を辞書で返す O(N)""" res = [[] for _ in range(self.n)] for i in range(self.n): x = self.find(i) res[x].append(i) return {r: res[r] for r in self.roots()} def __str__(self): return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots()) ######################################################### import sys input = sys.stdin.readline N,Q=map(int, input().split()) UF=WeightedUnionFind(N) W=[0]*N for _ in range(Q): t,a,b=map(int, input().split()) if t==1: a,b=a-1,b-1 a0,b0=UF.find(a),UF.find(b) UF.union(a0,b0,-W[a0]+W[b0]) elif t==2: x=UF.find(a-1) W[x]+=b else: a-=1 x=UF.find(a) print(W[x]+UF.diff(x,a))