Problem:

Weighted Union Find Trees

  There is a sequence $A = a_0, a_1, ..., a_{n-1}$. You are given the following information and questions.

relate$(x, y, z)$: $a_y$ is greater than $a_x$ by $z$

diff$(x, y)$: report the difference between $a_x$ and $a_y$ $(a_y - a_x)$

Input

$n \; q$
$query_1$
$query_2$
:
$query_q$

  In the first line, $n$ and $q$ are given. Then, $q$ information/questions are given in the following format.

0 $x \; y\; z$

  or

1 $x \; y$

where '0' of the first digit denotes the relate information and '1' denotes the diff question.

Output

For each diff question, print the difference between $a_x$ and $a_y$ $(a_y - a_x)$.

Constraints

  $2 \leq n \leq 100,000$

  $1 \leq q \leq 200,000$

  $0 \leq x, y < n$

  $x \ne y$

  $0 \leq z \leq 10000$

There are no inconsistency in the given information

Sample Input

5 6
0 0 2 5
0 1 2 3
1 0 1
1 1 3
0 1 4 8
1 0 4

Sample Output

2
?
10



Sample input:
5 6
0 0 2 5
0 1 2 3
1 0 1
1 1 3
0 1 4 8
1 0 4


Sample output:
2
?
10

Submission status: Accepted

Solution code:
class UnionFind:
  def __init__(self, n):
    self.tree = [-1] * n
    self.rank = [0] * n
    self.diff_weight = [0] * n
  
  def unite(self, a, b, w):
    w += self.weight(a)
    w -= self.weight(b)
    a = self.root(a)
    b = self.root(b)
    if a == b:
      return
    if self.rank[a] < self.rank[b]:
      a, b = b, a
      w *= -1
    if self.rank[a] == self.rank[b]:
      self.rank[a] += 1
    self.tree[b] = a
    self.diff_weight[b] = w
    
  def root(self, a):
    if(self.tree[a] < 0):
      return a
    else:
      res = self.root(self.tree[a])
      self.diff_weight[a] += self.diff_weight[self.tree[a]]
      self.tree[a] = res
      return self.tree[a]

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

  def weight(self, a):
    self.root(a)
    return self.diff_weight[a]

  def diff(self, a, b):
    return self.weight(b) - self.weight(a)

import sys

stdin = sys.stdin
na = lambda: map(int, stdin.readline().split())
ns = lambda: stdin.readline().rstrip()
ni = lambda: int(ns())

def main():
  n, m = na()
  uf = UnionFind(n)
  for _ in range(m):
    t = list(na())
    a, b, c = t[0], t[1], t[2]
    if a == 0:
      d = t[3]
      uf.unite(b, c, d)
    else:
      if uf.same(b, c):
        print(uf.diff(b, c))
      else:
        print("?")

main()

Submission status: Accepted

Solution code:
class UnionSet:
    def __init__(self, nmax: int) -> None:
        self.size = [1] * nmax
        self.id = [i for i in range(nmax)]
        self.weight = [0] * nmax

    def root(self, i: int) -> int:
        if (i == self.id[i]):
            return i
        else:
            tmp = self.root(self.id[i])
            self.weight[i] += self.weight[self.id[i]]
            self.id[i] = tmp
            return self.id[i]

    def get_weight(self, i: int) -> int:
        self.root(i)
        return self.weight[i]

    def connected(self, p: int, q: int) -> bool:
        return self.root(p) == self.root(q)

    def unite(self, p: int, q: int, w: int) -> None:
        w += self.get_weight(p)
        w -= self.get_weight(q)
        i, j = self.root(p), self.root(q)
        if (i == j):
            return
        if self.size[i] < self.size[j]:
            self.id[i] = j
            self.size[j] += self.size[i]
            self.weight[i] = -w
        else:
            self.id[j] = i
            self.size[i] += self.size[j]
            self.weight[j] = w

    def diff(self, p: int, q: int) -> None:
        i, j = self.root(p), self.root(q)
        if (i == j):
            print(self.get_weight(q) - self.get_weight(p))
        else:
            print("?")


if __name__ == "__main__":
    n, q = map(int, input().split())

    u = UnionSet(n)
    for _ in range(q):
        op, *v = map(lambda x: int(x), input().split())
        if (0 == op):
            x, y, w = v
            u.unite(x, y, w)
        else:
            x, y = v
            u.diff(x, y)

Submission status: Accepted

Solution code:
import sys
from sys import stdin,setrecursionlimit
sys.setrecursionlimit(10**6)
input=stdin.readline
#import pysnooper

class Weighted_Union_find:
    
    def __init__(self,n):
        self.n=n
        self.root=[i for i in range(n+1)]
        self.rank=[0]*(n+1)
        self.weight=[0]*(n+1)

    #@pysnooper.snoop()
    def find_root(self,x):# 頂点xのroot(根)頂点を見つける
        if self.root[x]==x:
            return x
        else:
            y=self.find_root(self.root[x])
            self.weight[x]+=self.weight[self.root[x]]
            self.root[x]=y
            return y
    #@pysnooper.snoop()
    def unite(self,x,y,w):#頂点xと頂点yを繋ぐ辺を追加
        rx=self.find_root(x)
        ry=self.find_root(y)
        if rx==ry:
            return 0
        if self.rank[rx]<self.rank[ry]:
            self.root[rx]=ry
            self.weight[rx]=w-self.weight[x]+self.weight[y]
        else:
            self.root[ry]=rx
            self.weight[ry]=-w-self.weight[y]+self.weight[x]
            if self.rank[rx]==self.rank[ry]:
                self.rank[rx]+=1

    def same(self,x,y):#頂点xと頂点yが連結であるか判定
        return self.find_root(x)==self.find_root(y)

    def count(self,x):#頂点xが属する木のサイズ
        return -self.root[self.find_root(x)]
    
    def diff(self,x,y):#頂点xから頂点yへのコスト
        return self.weight[x]-self.weight[y]

#@pysnooper.snoop()
def main():
    n,q=map(int,input().split())
    gragh=Weighted_Union_find(n+1)
    for _ in range(q):
        query=tuple(map(int,input().split()))
        if not query[0]:
            gragh.unite(query[1],query[2],query[3])
        else:
            if gragh.same(query[1],query[2]):
                print(gragh.diff(query[1],query[2]))
            else:
                print("?")
    #print(1111111111111111)
main()

Submission status: Accepted

Solution code:
class Node:
    
    def __init__(self, root, length, dist):
        self.root = root
        self.child = None
        self.length = length
        self.dist = dist
        self.tail = root
        
def relate(x, y, z):
    X = A[x].root
    Y = A[y].root
    if A[X].length > A[Y].length:
        x, y, z, X, Y = y, x, -z, Y, X
    T = A[Y].tail
    A[T].child = X
    A[Y].tail = A[X].tail
    A[Y].length += A[X].length
    tmp = X
    xd = A[x].dist
    yd = A[y].dist
    for _ in range(A[X].length):
        A[tmp].root = Y
        A[tmp].dist += yd - z - xd
        tmp = A[tmp].child
    
n,q = [int(i) for i in input().split()]
A = []
for i in range(n):
    A.append(Node(i, 1, 0))
for _ in range(q):
    c = [int(i) for i in input().split()]
    if c[0] == 0 and A[c[1]].root != A[c[2]].root:
        relate(c[1], c[2], c[3])
    elif c[0] == 1:
        if A[c[1]].root == A[c[2]].root:
            print(A[c[2]].dist - A[c[1]].dist)
        else:
            print("?")

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007

#1:set
#1_A
"""
n,q = map(int, input().split(" "))
group = [[i] for i in range(n)]
key = [i for i in range(n)]
for i in range(q):
    com, x, y = map(int, input().split(" "))
    if com == 0:
        if key[x] != key[y]:
            v = key[y]
            group[key[x]] = group[key[x]] + group[key[y]]
            for j in group[v]:
                key[j] = key[x]
            group[v] = []
    if com == 1:
        if key[x] == key[y]:
            print(1)
        else:
            print(0)
"""

#1_B 重み付きunionfind
def root(x):
    if par[x] == x:
        return x
    r = root(par[x])
    w[x] += w[par[x]]
    par[x] = r
    return par[x]

def same(x,y):
    return root(x) == root(y)

def unite(x,y,z):
    z += w[x]-w[y]
    x = root(x)
    y = root(y)
    if rank[x] < rank[y]:
        par[x] = y
        w[x] = -z
    else:
        par[y] = x
        w[y] = z
        if rank[x] == rank[y]:
            rank[x] += 1
n,Q = LI()
par = [i for i in range(n)]
rank = [0 for i in range(n)]
w = [0 for i in range(n)]
for _ in range(Q):
    q = LI()
    if q[0]:
        x,y = q[1],q[2]
        if same(x,y):
            print(w[y]-w[x])
        else:
            print("?")
    else:
        x,y,z = q[1:]
        if not same(x,y):
            unite(x,y,z)
#2:range quary
#2_A rmq
"""
def rmq(a,b,k,l,r):
    if r <= a or b <= l:
        return inf
    if a <= l and r <= b:
        return st[k]
    vl = rmq(a,b,2*k+1,l,(l+r)//2)
    vr = rmq(a,b,2*k+2,(l+r)//2,r)
    return min(vl,vr)

n,Q = LI()
n1 = 1
while n1 <= n:
    n1 *= 2
n = n1
inf = pow(2,31)-1
st = [inf for i in range(2*n-1)]
for _ in range(Q):
    q = LI()
    if not q[0]:
        x,y = q[1:]
        i = n+x-1
        st[i] = y
        while i > 0:
            i = (i-1)//2
            st[i] = min(st[2*i+1],st[2*i+2])
    else:
        a,b = q[1:]
        print(rmq(a,b+1,0,0,n))
"""

#2_B rsq
"""
def rsq(a,b,k,l,r):
    if r <= a or b <= l:
        return 0
        if a <= l and r <= b:
            return st[k]
            vl = rsq(a,b,2*k+1,l,(l+r)//2)
            vr = rsq(a,b,2*k+2,(l+r)//2,r)
            return vl+vr

            n,Q = LI()
            n1 = 1
            while n1 <= n:
                n1 *= 2
                n = n1
                st = [0 for i in range(2*n-1)]
                for _ in range(Q):
                    q = LI()
                    if not q[0]:
                        x,y = q[1:]
                        i = n+x-1
                        st[i] += y
                        while i > 0:
                            i = (i-1)//2
                            st[i] += y
                        else:
                            a,b = q[1:]
                            print(rsq(a,b+1,0,0,n))
"""
#2_C

#2_D
"""
def ruq(a,b,k,l,r,z):
    if r <= a or b <= l:
        return
    if a <= l and r <= b:
        st[k] = z
        return
    vl = ruq(a,b,2*k+1,l,(l+r)//2,z)
    vr = ruq(a,b,2*k+2,(l+r)//2,r,z)
    return

n,Q = LI()
n1 = 1
while n1 <= n:
    n1 *= 2
n = n1
d = pow(2,31)-1
st = [d for i in range(2*n-1)]
for _ in range(Q):
    q = LI()
    if not q[0]:
        x,y,z = q[1:]
        ruq(x,y+1,0,0,n,z)
    else:
"""
#2_E

#2_F

#2_G

#2_H

#2_I


#3:sliding window
#3_A
"""
n,s = MI()
a = LI()
for i in range(1,n):
    a[i] += a[i-1]
a.insert(0,0)
l = 0
r = 0
ans = float("inf")
if a[1] >= s:
    print(1)
    quit()
while r < n:
    r += 1
    if a[r]-a[l] >= s:
        while a[r]-a[l] >= s and l < r:
            l += 1
        ans = min(ans, r-l+1)
if ans == float("inf"):
    print(0)
    quit()
print(ans)
"""

#3_B
"""
n,k = MI()
a = LI()
l = 0
r = 0
ans = float("inf")
fl = [0 for i in range(k+1)]
s = 0
if k == 1 and a[0] == 1:
    print(1)
    quit()
if a[0] <= k:
    fl[a[0]] = 1
    s = 1
while r < n-1:
    r += 1
    if a[r] <= k:
        if not fl[a[r]]:
            s += 1
        fl[a[r]] += 1
    if s == k:
        while s == k:
            l += 1
            if a[l-1] <= k:
                if fl[a[l-1]] == 1:
                    s -= 1
                fl[a[l-1]] -= 1
        ans = min(ans, r-l+2)
if ans == float("inf"):
    print(0)
    quit()
print(ans)
"""

#3_C
"""
n,q = LI()
a = LI()
x = LI()
for i in range(q):
    ans = 0
    r = -1
    s = 0
    for l in range(n):
        while r+1 < n and s+a[r+1] <= x[i]:
            r += 1
            s += a[r]
        if s <= x[i]:
            ans += r-l+1
        if l == r:
            r += 1
            if r < n:
                s += a[r]
        s -= a[l]
    print(ans)
"""


#3_D
"""
n,l = LI()
a = LI()
k = [0 for i in range(l)]
for i in range(l):
    k[i] = a[i]
k.sort()
ans = [k[0]]
for i in range(n-l):
    j = bisect.bisect_left(k,a[i])
    x = k.pop(j)
    j = bisect.bisect_left(k,a[l+i])
    k.insert(j,a[l+i])
    ans.append(k[0])
for i in range(len(ans)-1):
    print(ans[i],end = " ")
print(ans[-1])
"""

#4:coordinate compression
#4_A
"""
n = int(sys.stdin.readline())
d = defaultdict(int)
lx = []
ly = []
for i in range(n):
    x,y,s,t = map(int,sys.stdin.readline()[:-1].split())
    d[(x,y)] += 1
    d[(x,t)] -= 1
    d[(s,y)] -= 1
    d[(s,t)] += 1
    i = bisect.bisect_left(lx,x)
    if i >= len(lx) or lx[i] != x:
        lx.insert(i,x)
    i = bisect.bisect_left(ly,y)
    if i >= len(ly) or ly[i] != y:
        ly.insert(i,y)
    i = bisect.bisect_left(lx,s)
    if i >= len(lx) or lx[i] != s:
        lx.insert(i,s)
    i = bisect.bisect_left(ly,t)
    if i >= len(ly) or ly[i] != t:
        ly.insert(i,t)

for x in lx:
    for j in range((len(ly))-1):
        d[(x,ly[j+1])] += d[(x,ly[j])]
for y in ly:
    for i in range((len(lx))-1):
        d[(lx[i+1],y)] += d[(lx[i],y)]
ans = 0
for j in range(len(ly)-1):
    y = ly[j]
    p_y = ly[j+1]
    for i in range(len(lx)-1):
        x = lx[i]
        p_x = lx[i+1]
        if d[(x,y)] >= 1:
            ans += (p_y-y)*(p_x-x)
print(ans)
"""
#5:comulative sum
#5_A
"""
n,t = map(int, input().split(" "))
num = [0 for i in range(t)]
for i in range(n):
    l,r = map(int, input().split(" "))
    num[l] += 1
    if r < t:
        num[r] -= 1
for i in range(1,t):
    num[i] += num[i-1]
print(max(num))
"""

#5_B
"""
n = int(input())
lec = [[0 for i in range(1001)] for j in range(1001)]
max_x = 0
max_y = 0
for i in range(n):
    x,y,s,t = map(int, input().split(" "))
    lec[y][x] += 1
    lec[y][s] -= 1
    lec[t][x] -= 1
    lec[t][s] += 1
    max_x = max(max_x, s)
    max_y = max(max_y, t)

for i in range(max_y+1):
    for j in range(1, max_x+1):
        lec[i][j] += lec[i][j-1]

for i in range(1, max_y+1):
    for j in range(max_x+1):
        lec[i][j] += lec[i-1][j]

ans = 0
for i in range(max_y+1):
    for j in range(max_x+1):
        ans = max(ans, lec[i][j])

print(ans)
"""

Submission status: Accepted

Solution code:
line = input()
n, q = list(map(int, line.split()))
rel = {}
for i in range(0, n):
    rel[i] = []
parent = [i for i in range(0, n)]
rank = [0] * n
weight = [0] * n

def find(x):
    if parent[x] == x:
        return x
    else:
        y = find(parent[x])
        weight[x] += weight[parent[x]]
        parent[x] = y
        return y

def union(x, y, w):
    rx = find(x)
    ry = find(y)
    if rank[rx] < rank[ry]:
        parent[rx] = ry
        weight[rx] = w - weight[x] + weight[y]
    else:
        parent[ry] = rx
        weight[ry] = - w - weight[y] + weight[x]
        if rank[rx] == rank[ry]:
            rank[rx] += 1

def same(x, y):
    return find(x) == find(y)

def diff(x, y):
    return weight[x] - weight[y]

for _ in range(0, q):
    line = input()
    query = list(map(int, line.split()))
    if query[0] == 0:
        x, y, z = query[1:]
        union(x, y, z)
    elif query[0] == 1:
        x, y = query[1:]
        if same(x, y):
            print(diff(x, y))
        else:
            print("?")

Submission status: Accepted

Solution code:
class WeightedUnionFind:
    def __init__(self, N):
        # negative value: represents the root of a tree; its absolute value is the size of the tree
        # positive value: the parent's index
        self.vertices = [-1 for _ in range(N)]
        self.rank = [0] * N
        self.diff_weight = [0] * N
    
    def weight(self, v):
        self.find(v) # path compression
        return self.diff_weight[v]
    
    def dist(self, u, v):
        if self.is_connected(x, y):
            return self.weight(v) - self.weight(u)
        else:
            return None
    
    def find(self, v):
        if self.vertices[v] < 0:
            return v
        else:
            # path compression: reconnect v to the root
            root = self.find(self.vertices[v])
            self.diff_weight[v] += self.diff_weight[self.vertices[v]]
            self.vertices[v] = root
            return self.vertices[v]
    
    def union(self, u, v, w):
        s1 = self.find(u) # the root of the tree including vertex u
        s2 = self.find(v) # the root of the tree including vertex v
        
        if s1 == s2: # u and v is in the same tree
            return False
        
        if self.rank[s1] > self.rank[s2]: # the tree including u is taller
            self.vertices[s1] += self.vertices[s2] # update the size of the bigger tree
            self.vertices[s2] = s1
            self.diff_weight[s2] = w - self.diff_weight[v] + self.diff_weight[u]
        else: # the tree including v is taller
            self.vertices[s2] += self.vertices[s1] # update the size of the bigger tree
            self.vertices[s1] = s2
            self.diff_weight[s1] = -w - self.diff_weight[u] + self.diff_weight[v]
            if self.rank[s1] == self.rank[s2]:
                self.rank[s2] += 1
        return True
        
    def is_connected(self, u, v):
        return self.find(u) == self.find(v)
    
    def size(self, v):
        return -self.vertices[self.find(v)]
    
n, q = map(int, input().split())
wuf = WeightedUnionFind(n)
for _ in range(q):
    txt = input().split()
    if txt[0] == '0':
        x, y, z = map(int, txt[1:])
        wuf.union(x, y, z)
    else:
        x, y = map(int, txt[1:])
        res = wuf.dist(x, y)
        if res is not None:
            print(res)
        else:
            print('?')

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
class Union():
    def __init__(self, n):
        self.par = [i for  i in range(n+1)]
        self.rank = [0]*(n+1)
        self.weight = [0]*(n+1) #子から親までの距離
        
    def find(self, x):
        if self.par[x] == x:
            return x
        y = self.find(self.par[x])
        self.weight[x] += self.weight[self.par[x]]
        self.par[x] = y
        return y
    
    def union(self, x, y, w):
        rx = self.find(x)
        ry = self.find(y)
        if self.rank[rx] < self.rank[ry]:
            self.par[rx] = ry
            self.weight[rx] = w - self.weight[x] + self.weight[y]
        else:
            self.par[ry] = rx
            self.weight[ry] = -w - self.weight[y] + self.weight[x]
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1
        
    def same(self, x, y):
        return (self.find(x) == self.find(y))
    
    #ｘからｙへの距離
    def diff(self, x, y):
        if self.same(x,y):
            return self.weight[x] - self.weight[y]
        else:return '?'

n ,q = map(int, input().split())
unite = Union(n)
for i in range(q):
    a, b, c, *d = map(int, input().split())
    if a == 0:unite.union(b,c,d[0])
    else:print(unite.diff(b,c))

Submission status: Accepted

Solution code:
idx_com = 0
idx_x = 1
idx_y = 2
idx_z = 3

n, nq = map(int, input().split())
parents = list(range(n))
ranks = [0] * n
weights = [0] * n

def find(x):
    if parents[x] == x:
        return x
    y = find(parents[x])
    weights[x] += weights[parents[x]]
    parents[x] = y
    return y

def unite(x, y, w):
    root_x = find(x)
    root_y = find(y)

    if ranks[root_x] < ranks[root_y]:
        parents[root_x] = root_y
        weights[root_x] = -w - weights[x] + weights[y]
    else:
        parents[root_y] = root_x
        weights[root_y] = +w - weights[y] + weights[x]
        if ranks[root_x] == ranks[root_y]:
            ranks[root_x] += 1

def same(x, y):
    return find(x) == find(y)

def diff(x, y):
    return weights[y] - weights[x]

for _ in range(nq):
    q = list(map(int, input().split()))
    if q[idx_com] == 0:
        unite(q[idx_x], q[idx_y], q[idx_z])
    else:
        if same(q[idx_x], q[idx_y]):
            print(diff(q[idx_x], q[idx_y]))
        else:
            print("?")

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

def findSet(x):
  if x == parent[x]:
    return x
  else:
    temp = parent[x]
    parent[x] = findSet(parent[x])
    weight[x] += weight[temp]
    return parent[x]
  
def link(x, y, z):
  a = findSet(x)
  b = findSet(y)
  if a != b:
    parent[b] = a
    weight[b] = weight[x] - weight[y] + z

n, q = list(map(int, input().split()))

data = (i for i in range(n))
parent = [i for i in range(n)]
weight = [0 for i in range(n)]

for i in range(q):
  Ltemp = list(map(int, input().split()))
  if len(Ltemp) == 4:
    x, y, z = Ltemp[1:]
    link(x, y, z)
  else:
    x, y = Ltemp[1:]
    if findSet(x) == findSet(y):
      print(weight[y] - weight[x])
    else:
      print('?')

Submission status: Accepted

Solution code:
import sys
import time
sys.setrecursionlimit(20000)

def find(tree,x):
    (idx,weight) = tree[x]
    if(idx== -1):
        return x
    else:
        root_idx = find(tree,idx)
        tree[x] = (root_idx, tree[x][1] + tree[idx][1])
        return root_idx

def relate(tree,x,y,z):
    x_root_idx = find(tree,x)
    y_root_idx = find(tree,y)
    if(x_root_idx == y_root_idx):
        return False
    
    if (tree_rank[y_root_idx] < tree_rank[x_root_idx]):
        tree[y_root_idx] = (x_root_idx, z+tree[x][1]-tree[y][1])
    else:
        tree[x_root_idx] = (y_root_idx, -z-tree[x][1]+tree[y][1])
        if(tree_rank[x_root_idx]==tree_rank[y_root_idx]):
            tree_rank[y_root_idx] = tree_rank[y_root_idx] + 1
    #tree[x_root_idx] = (y_root_idx,z-tree[x_root_idx][1]+tree[y_root_idx][1])

def diff(tree,x,y):
    x_idx = find(tree,x)
    y_idx = find(tree,y)
    if not(x_idx == y_idx):
        return "?"
    return tree[y][1] - tree[x][1]

if __name__ == '__main__':
    N,query_num = map(int, input().split())
    weighted_union_find_tree = [(-1,0) for _ in range(N)]
    tree_rank = [0]*N
    for i in range(query_num):
        query = list(map(int,input().split()))
        if(query[0]==0):
            relate(weighted_union_find_tree,query[1],query[2],query[3])
            #print(weighted_union_find_tree)
            #print(tree_rank)
        elif(query[0]==1):
            res = diff(weighted_union_find_tree,query[1],query[2])
            print(res)

Submission status: Accepted

Solution code:


class UnionFind():

    def __init__(self, s):
        self.nodes = [-1 for _ in range(s)]
        self.rank = [0 for _ in range(s)]
        self.weight = [0 for _ in range(s)]

    def find(self, x):
        if self.nodes[x] < 0:
            return x
        else:
            root = self.find(self.nodes[x])
            self.weight[x] += self.weight[self.nodes[x]]
            self.nodes[x] = root
            return root

    def union(self, x, y, z):
        s_1 = self.find(x)
        s_2 = self.find(y)
        if s_1 == s_2:
            return False
        if self.rank[s_1] < self.rank[s_2]:
            self.nodes[s_1] = s_2
            self.weight[s_1] = z - self.weight[x] + self.weight[y]
        elif self.rank[s_1] > self.rank[s_2]:
            self.nodes[s_2] = s_1
            self.weight[s_2] = self.weight[x] - self.weight[y] - z
        else:
            self.nodes[s_2] = s_1
            self.weight[s_2] = self.weight[x] - self.weight[y] - z
            self.rank[s_1] += 1
        return True

    def is_same(self, x, y):
        return self.find(x) == self.find(y)

    def diff(self, x, y):
        return self.weight[x] - self.weight[y]


if __name__ == "__main__":
    n, q = map(int, input().split())
    sets = UnionFind(n)
    for i in range(q):
        inputs = [int(i) for i in input().split()]
        if inputs[0] == 0:
            sets.union(inputs[1], inputs[2], inputs[3])
        else:
            if sets.is_same(inputs[1], inputs[2]):
                print(sets.diff(inputs[1], inputs[2]))
            else:
                print("?")

Submission status: Accepted

Solution code:
import sys

class WeightedUnionFind:
    def __init__(self, N:int):
        """N: 大きさ
        size: 連結成分の大きさ
        weight: rootからの重み
        """
        self.par = [i for i in range(N)]
        #self.size = [1]*N
        self.rank = [0]*N
        self.weight = [0]*N

    def root(self, x:int)->int:
        """根を求める"""
        if self.par[x] == x: # if root
            return x
        else:
            root_x = self.root(self.par[x]) # 経路圧縮
            self.weight[x] += self.weight[self.par[x]]
            self.par[x] = root_x
            return root_x

    def get_weight(self, x: int)->int:
        """x の重みを取得"""
        self.root(x) # 経路圧縮
        return self.weight[x]

    def get_diff(self, x:int, y:int)->int:
        """x と y の差分を取得"""
        if not self.is_same(x, y): return "?" # 判定不可
        return self.get_weight(y) - self.get_weight(x)

    def is_same(self, x:int, y:int)->bool:
        """x と y が同じ集合に属するか否か"""
        return self.root(x)==self.root(y)

    def unite(self, x:int, y:int, w:int)->bool:
        """weight[y] = weight[x]+w となるようにmerge(x が y の親)
        return True if merge 可能"""
        if self.is_same(x, y): return False
        root_x = self.root(x)
        root_y = self.root(y)
        w += (self.weight[x] - self.weight[y])
        if self.rank[root_x] < self.rank[root_y]:
            self.par[root_x] = root_y
            self.weight[root_x] = -w
        else:
            self.par[root_y] = root_x
            self.weight[root_y] = w
            if self.rank[root_x] == self.rank[root_y]:
                self.rank[root_x] += 1
        return True

    def get_size(self, x:int)->int:
        """xの属するグループのサイズ"""
        return self.size[self.root(x)]

if __name__ == "__main__":
    N,Q = map(int, sys.stdin.readline().split())
    UNITE,DIFF = 0,1
    wuf = WeightedUnionFind(N)
    for _ in range(Q):
        com,*x = map(int, sys.stdin.readline().split())
        if com==UNITE:
            wuf.unite(*x)
        else: # same
            print(wuf.get_diff(*x))

Submission status: Accepted

Solution code:
class P_UnionFind:
    def __init__(self, n):
        self.p=[i for i in range(n)]
        self.r=[0 for i in range(n)]
        self.d=[0 for i in range(n)]
    def root(self,x):
        if self.p[x]==x:
            return x
        else:
            tmp = self.root(self.p[x])
            self.d[x] += self.d[self.p[x]]
            self.p[x] = tmp
            return self.p[x]
    
    def weight(self,x):
        self.root(x)
        return self.d[x]

    def diff(self,x,y):
        if self.root(x)==self.root(y):
            return self.weight(y)-self.weight(x)
        else:
            return '?'

    def uni(self,x,y,w):
        w+=self.weight(x)
        w-=self.weight(y)
        x=self.root(x)
        y=self.root(y)
        if(x==y):
            return
        if self.r[x]<self.r[y]:
            self.p[x]=y
            self.d[x]=-w
        else:
            self.p[y]=x
            self.d[y]=w
            if self.r[x]==self.r[y]:
                self.r[x]+=1
    
    def same(self,x,y):
        return self.root(x)==self.root(y)

n,q=map(int,input().split())
uf=P_UnionFind(n)
ans=[]
for i in range(q):
    d=list(map(int,input().split()))
    if d[0]==0:
        c,x,y,z=d
        uf.uni(x,y,z)
    else:
        c,x,y=d
        ans.append(uf.diff(x,y))
print(*ans,sep='\n')

Submission status: Accepted

Solution code:
n,q=map(int,input().split())
Q=[list(map(int,input().split())) for i in range(q)]

#UnionFind

Group=[[i,0] for i in range(n)]#グループ分け.Group[i]=jのときiとjは同じグループ

def find(x):#find(a)=find(b)のとき同じグループ
    ANS=Group[x][1]
    while Group[x][0] != x:
        x=Group[x][0]
        ANS+=Group[x][1]
    return x,ANS

def Union(x,y,z):  # xとyが同じグループになるよう更新
    if find(x)[0] != find(y)[0]:
        MIN=min(find(x)[0],find(y)[0])
        if find(x)[0]==MIN:
            Group[find(y)[0]]=[MIN,z+find(x)[1]-find(y)[1]]
        else:
            Group[find(x)[0]]=[MIN,-z+find(y)[1]-find(x)[1]]
            

for query in Q:
    if query[0]==0:
        Union(query[1],query[2],query[3])
        #print(Group)
    else:
        if find(query[1])[0]==find(query[2])[0]:
            print(find(query[2])[1]-find(query[1])[1])
        else:
            print("?")

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
write = sys.stdout.write

N, Q = map(int, readline().split())
*p, = range(N)
data = [0]*N
def root(x):
    if x == p[x]:
        return x
    r = p[x]
    p[x] = y = root(r)
    data[x] += data[r]

    return y
def unite(x, y, z):
    px = root(x); py = root(y)
    if px == py:
        return 0
    if px < py:
        p[py] = px
        data[py] = data[x] - data[y] - z
    else:
        p[px] = py
        data[px] = data[y] - data[x] + z
    return 1


ans = []
for q in range(Q):
    t, *cmd = map(int, readline().split())
    if t:
        x, y = cmd
        px = root(x); py = root(y)
        if px == py:
            ans.append(str(data[x] - data[y]))
        else:
            ans.append("?")
    else:
        x, y, z = cmd
        unite(x, y, z)
write("\n".join(ans))
write("\n")

Submission status: Runtime Error

Solution code:
MAX = 10003 
N, Q =  (int(x) for x in  input().split())
ws = [0 for i in range(MAX)] 
par = [-1 for i in range(N)]

def weight(x):
    root(x)
    return ws[x]

def root(x):
    if par[x] < 0: return x
    p = root(par[x])
    ws[x] = ws[x] + ws[par[x]]
    par[x] = p
    return par[x]
    return y


def unite(y, x, z):
    z = z + weight(x)
    z = z - weight(y)
    x = root(x)
    y = root(y)
    if x == y: return 0
    if par[y] < par[x]:
        tmp = x
        x = y 
        y = tmp 
        z = -z
     
    par[x] = par[x] + par[y]
    par[y] = x
    ws[y] = z
    return 1 

def diff(x,y):
    if root(x) != root(y) :return False
    ans = ws[x] - ws[y]
    return ans



for q in range(Q):
    t, *cmd =  (int(x) for x in  input().split())
    if t:
        x, y = cmd
        z = diff(x, y)
        if z==False:print("?")
        else :print(z)
    else:
        x, y, z = cmd
        unite(x, y, z)

Submission status: Runtime Error

Solution code:
import sys

def simplefindset(x,element,resultPos=0):
    if(x != element[x]):
        resultPos = simplefindset(element[x],element,resultPos)
    else:
        resultPos = x
    return resultPos

def findset(x,element,weight,resultPos=0,sumW=0):
    if(x != element[x]):
        resultPos,sumW = findset(element[x],element,weight,resultPos,sumW)
    else:
        resultPos = x
    sumW += weight[x]
    return resultPos,sumW

def union(x,y,element,weight,w):
    x,wx = findset(x,element,weight)
    y,wy = findset(y,element,weight)
    link(x,wx,y,wy,w,element)
def link(x,wx,y,wy,z,element):
    z = z+wy-wx

    element[x] = y
    weight[x] = z

n,q = map(int, input().split());

element = [i for i in range(n)]
weight = [0 for i in range(n)]

for i in range(q):
    inp = map(int, input().split());
    inp = list(inp)    
    if(inp[0] == 0):
        x,y,w = inp[1],inp[2],inp[3]
        union(x,y,element,weight,w)
    else:
        x,y = inp[1],inp[2]
        if(simplefindset(x,element) == simplefindset(y,element)):
            x,wx = findset(x,element,weight)
            y,wy = findset(y,element,weight)
            print(wx-wy)
        else:
            print('?')