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:
par = [i for i in range(100)]
rank = [0 for i in range(100)]
weight_to_root = [0 for i in range(100)]

def find(x):
    if par[x] == x:
        return x
    else:
        root = find(par[x])
        weight_to_root[x] += weight_to_root[par[x]]
        par[x] = root
        return root

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

def union(x,y,w):
    a = find(x)
    b = find(y)
    if a==b:
        return False
    if rank[a] > rank[b]:
        par[b] = a
        weight_to_root[b] = -w - weight_to_root[y] + weight_to_root[x]
    elif rank[a] < rank[b]:
        par[a] = b
        weight_to_root[a] = w - weight_to_root[x] + weight_to_root[y]
    else:
        par[b] = a
        weight_to_root[b] = -w - weight_to_root[y] + weight_to_root[x]
        rank[a] += 1
    return True

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


def main():
    global rank,par,weight_to_root
    n,q = [int(i) for i in input().split()]
    rank = [0 for i in range(n)]
    par = [i for i in range(n)]
    weight_to_root = [0 for i in range(n)]
    for i in range(q):
        s = [int(j) for j in input().split()]
        if s[0] == 0:
            union(s[1],s[2],s[3])
        else:
            if is_same(s[1],s[2]):
                print(diff(s[1],s[2]))
            else:
                print('?')

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

class WeightedUnionFind:
    def __init__(self, N):
        self.parent = list(range(N))
        self.rank = [0] * N
        self.weight = [0] * N

    def find(self, x):
        stack = [x]
        while self.parent[x] != x:
            x = self.parent[x]
            stack.append(x)
        r = stack[-1]
        while stack:
            x = stack.pop()
            self.weight[x] += self.weight[self.parent[x]]
            self.parent[x] = r
        return r

    def unite(self, x, y, w):
        rx = self.find(x)
        ry = self.find(y)
        w += self.weight[x] - self.weight[y]
        x = rx
        y = ry
        if x == y:
            return False

        if self.rank[x] < self.rank[y]:
            x, y = y, x
            w = -w
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1
        self.parent[y] = x
        self.weight[y] = w
        return True

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

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

n, q = map(int, input().split())
wuf = WeightedUnionFind(n)
for _ in range(q):
    t, *data = map(int, input().split())
    if t == 0:
        x, y, z = data
        wuf.unite(x, y, z)
    else:
        x, y = data
        if not wuf.same(x, y):
            print('?')
        else:
            print(wuf.diff(x, y))

Submission status: Accepted

Solution code:
# N,M = map(int,sys.stdin.readline().split())
# a = tuple(map(int,sys.stdin.readline().split())) # single line with multi param
# a = tuple(int(sys.stdin.readline()) for _ in range(N)) # multi line with single param
# a = tuple(tuple(map(int,sys.stdin.readline().rstrip().split())) for _ in range(N)) # multi line with multi param
# s = sys.stdin.readline().rstrip()
# N = int(sys.stdin.readline())
# INF = float("inf")

import sys
sys.setrecursionlimit(1000000)
N,Q = map(int,sys.stdin.readline().split())
qs = tuple(tuple(map(int,sys.stdin.readline().rstrip().split())) for _ in range(Q)) # multi line with multi param

parents = list(range(N))
diffs = [0]*N

def root(x):
    if parents[x]==x:
        return x
    else:
        pr = root(parents[x])
        diffs[x] += diffs[parents[x]]
        parents[x] = pr
        return pr

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

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

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

# make sure weight(y)-weight(x)=w
def merge(x,y,w):
    # assume ry > rx
    rx = root(x)
    ry = root(y)
    # incase rx!=x and ry !=y
    diff = weight(x)+(w-weight(y))
    if rx == ry:
        return False
    if rx < ry:
        rx,ry,diff = ry,rx,-diff
    diffs[ry] = diff
    parents[ry] = rx
    return True

for q in qs:
    if q[0]==0:
        x,y,z = q[1:]
        merge(x,y,z)
    else:
        x,y = q[1:]
        if root(x)==root(y):
            print(diff(x,y))
        else:
            print("?")

Submission status: Accepted

Solution code:
# https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/1/DSL_1_A


class WeightedUnionFind:
    """
    重み付きUnionFind

    """
    root_position = 0

    def __init__(self, size: int):
        self.size = size
        # 負の値はルート (集合の代表) で集合の個数
        # 正の値は次の要素を表す
        self.parent = [-1] * size
        self.weight = [WeightedUnionFind.root_position] * size

    def find(self, x: int) -> (int, int):
        """
        xを含む集合の代表とxの代表からの位置を求める
        """
        if self.parent[x] < 0:
            return x, self.weight[x]
        # 集合の代表にリンクを繋ぎ変える
        same_group_items = []
        y = x
        while self.parent[y] >= 0:
            same_group_items.append(y)
            y = self.parent[y]
        w = 0
        while same_group_items:
            child = same_group_items.pop()
            w += self.weight[child]
            self.weight[child] = w
            self.parent[child] = y
        return y, self.weight[x]

    def unite(self, x: int, y: int, weight: int) -> bool:
        """
        xを含む集合とyを含む集合を併合する
        `weight[x] + weight = weight[y]`になるように辺に重みをもたせる。
        xとyがすでに同じ集合に含まれている場合Falseを返す。
        """
        root_x, weight_x = self.find(x)
        root_y, weight_y = self.find(y)

        if root_x == root_y:
            return False

        if self.parent[root_x] >= self.parent[root_y]:
            self.parent[root_x] += self.parent[root_y]
            self.parent[root_y] = root_x
            self.weight[root_y] = weight_x + weight - weight_y
        else:
            self.parent[root_y] += self.parent[root_x]
            self.parent[root_x] = root_y
            self.weight[root_x] = weight_y - weight - weight_x

        return True


def solve():
    n, q = map(int, input().split())
    uf = WeightedUnionFind(n)
    for _ in range(q):
        query = list(map(int, input().split()))
        if query[0] == 0:
            _, x, y, z = query
            uf.unite(x, y, z)
        else:
            _, x, y = query
            root_x, pos_x = uf.find(x)
            root_y, pos_y = uf.find(y)
            if root_x == root_y:
                print(pos_y - pos_x)
            else:
                print('?')


if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
def root(x):
    if(par[x]==x):
        return x
    else:
        r=root(par[x])
        diff_weight[x]+=diff_weight[par[x]]
        par[x]=r
        return r

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

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

def relate(a,b,w):
    w+=weight(a);w-=weight(b)
    a=root(a)
    b=root(b)
    if(a==b):
        return False
    if rank[a]<rank[b]:
        a,b=b,a
        w=-w
    if rank[a]==rank[b]:
        rank[b]+=1
        par[b]=a
    par[b]=a
    diff_weight[b]=w
    siz[a]+=siz[b]
    return True

def size(a):
    return siz[root(a)]
    
def same(a,b):
    return root(a)==root(b)
    
N,Q=map(int,input().split())
par=[i for i in range(N)]
siz=[1 for _ in range(N)]
rank=[0 for _ in range(N)]
diff_weight=[0 for _ in range(N)]
for i in range(Q):
    query=list(map(int,input().split()))
    if not query[0]:
        X,Y,W=query[1:]
        relate(X,Y,W)
    else:
        X,Y=query[1:]
        if same(X,Y):
            print(diff(X,Y))
        else:
            print('?')

Submission status: Accepted

Solution code:
import sys 
input = sys.stdin.readline


class UnionFindWeighted:
    """ポテンシャル付きUnionFind"""
    def __init__(self, n):
        self.parent = [-1] * n
        self.weight = [0] * n
        self.cnt = n
        self.INF = 10 ** 18
       
    def root(self, x):
        """頂点xの根を求める"""
        if self.parent[x] < 0:
            return x
        rt = self.root(self.parent[x])
        self.weight[x] += self.weight[self.parent[x]]
        self.parent[x] = rt
        return rt

    def merge(self, x, y, weight):
        """頂点xを含む集合と頂点y含む集合を結合する
        weight: 頂点yに対する頂点xのポテンシャル(頂点xの方がweight高い)
        """
        root_x = self.root(x)
        root_y = self.root(y)
        if root_x == root_y:
            return
        if self.parent[root_x] < self.parent[root_y]:
            self.parent[root_x] += self.parent[root_y]
            self.parent[root_y] = root_x
            self.weight[root_y] = -weight + self.weight[x] - self.weight[y]
        else:
            self.parent[root_y] += self.parent[root_x]
            self.parent[root_x] = root_y
            self.weight[root_x] = weight - self.weight[x] + self.weight[y]
        self.cnt -= 1

    def is_same(self, x, y):
        """頂点x, yが同じ集合に属するかどうかを返す"""
        return self.root(x) == self.root(y)

    def diff(self, x, y):
        """頂点yに対する頂点xのポテンシャルを求める
        ただし、頂点x,y間にポテンシャルが定義されていない場合は INF を返す
        """
        if not self.is_same(x, y):
            return self.INF
        return self.weight[x] - self.weight[y]

    def get_size(self, x):
        """頂点xを含む集合の要素数を返す"""
        return -self.parent[self.root(x)]

    def get_cnt(self):
        """集合の個数を返す"""
        return self.cnt


def solve():
    n, q = list(map(int, input().split()))
    query = [list(map(int, input().split())) for i in range(q)]
    INF = 10 ** 18
    ufw = UnionFindWeighted(n)

    for i in range(q):
        if query[i][0] == 0:
            # クエリ1の場合
            _, x, y, weight = query[i]
            ufw.merge(x, y, weight)
        else:
            # クエリ2の場合
            _, x, y = query[i]
            ans = ufw.diff(x, y)
            if ans == INF:
                print("?")
            else:
                print(ans)


if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import math

class weightedUnionTree:
    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
        else:
            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)
        #self.isThere[x] = True; self.isThere[y] = True

        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):
        """
        print("diff: ",end="")
        print(self.weight[x],end=" ")
        print(self.weight[y],end=" ")
        #print(self.isThere)
        """

        if(self.same(x, y)): #conditional branch
            print(self.weight[x] - self.weight[y])
        else:
            print("?")


if __name__ == "__main__":
    n, q = (int(p) for p in input().split())
    tree = weightedUnionTree(n)
    #for i in range(n):
    #    queue.append(0)
    for i in range(q):
        question, num = input().split(' ', 1)
        #print(question)
        #print(input)
        if(int(question) == 0):
            #print("relate")
            x, y, z = num.split(' ')
            tree.union(int(x), int(y), int(z))
        else:
            #print("diff")
            x, y = num.split(' ')
            tree.diff(int(x), int(y))

Submission status: Accepted

Solution code:
rank = []
p = []
w = []

def makeSet(x):
    p.append(x)
    rank.append(0)
    w.append(0)


def union(x, y):
    link(findSet(x), findSet(y))


def link(x, y):
    if rank[x] > rank[y]:
        p[y] = x

    else:
        p[x] = y
        if rank[x] == rank[y]:
            rank[y] = rank[y] + 1


def findSet(x):
    if p[x] == x:
        return x

    i = findSet(p[x])
    w[x] += w[p[x]]
    p[x] = i
    return i


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

def relate (x,y,z):
    i = findSet(x)
    j = findSet(y)

    if rank[i] < rank[j]:
        p[i] = j
        w[i] = z - w[x] + w[y]
    else:
        p[j] = i
        w[j] = -z - w[y] + w[x]
        if rank[i] == rank[j]:
            rank[i] += 1

n, q = map(int, input().split())
for i in range(n):
    makeSet(i)
for i in range(q):
    com, *cmd = map(int, input().split())
    if com == 0:
        relate(cmd[0], cmd[1],cmd[2])
    else:
        x, y = cmd
        if same(x, y):
            print(w[x] - w[y])
        else:
            print("?")

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(50000)

def findSet(x,element,weight):
    if(x != element[x]):
        element[x],s = findSet(element[x],element,weight)
        weight[x] += s

    return element[x],weight[x]

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]
        x,wx = findSet(x,element,weight)
        y,wy = findSet(y,element,weight)

        if(x == y):
            print(wx - wy)
        else:
            print('?')

Submission status: Accepted

Solution code:
class WeightedUnionFind():
    def __init__(self,n):
        self.n=n
        self.parents=[-1]*n
        self.differ=[0]*n

    def find(self,x):
        if self.parents[x]<0:
            return x
        else:
            r=self.find(self.parents[x])
            self.differ[x]+=self.differ[self.parents[x]]
            self.parents[x]=r
            return self.parents[x]

    def unite(self,x,y,w):
        xp=self.find(x)
        yp=self.find(y)
        w=w+self.differ[x]-self.differ[y]

        if xp!=yp:
            if self.parents[xp]>self.parents[yp]:
                xp,yp=yp,xp
                w=-w

            self.parents[xp]+=self.parents[yp]
            self.parents[yp]=xp
            self.differ[yp]=w

    def diff(self,x,y):
        xp=self.find(x)
        yp=self.find(y)
        if xp==yp:
            return True,self.differ[y]-self.differ[x]
        else:
            return False,0

n,q=map(int,input().split())
WUF=WeightedUnionFind(n)
for i in range(q):
    query=list(map(int,input().split()))
    if query[0]==0:
        WUF.unite(query[1],query[2],query[3])
    elif query[0]==1:
        judge,diff=WUF.diff(query[1],query[2])
        if judge:
            print(diff)
        else:
            print("?")

Submission status: Accepted

Solution code:
class WeightedUnionFindTree():
    '''ランク付きUnionFind木'''
    def __init__(self, n):
        ''' 初期化 '''
        self.par = list(range(n))#自分自信を根とする
        self.rank = [0] * n # 木の高さ 最初は0
        self.w = [0] * n # 重み

    def root(self, x):
        ''' 木の根を求める '''
        if self.par[x] == x:#自分が根ノードなら
            return x

        root = self.root(self.par[x])
        self.w[x] += self.w[self.par[x]]# 累積和をとる
        self.par[x] = root
        return root
    def relate(self, x, y, weight=0):
        # x と y の root へ (x と y が既につながっていたらreturn
        root_x, root_y = self.root(x), self.root(y)
        if root_x == root_y: return;
        #木の高さ-ランクが低い方に繋げる
        if self.rank[root_x] < self.rank[root_y]:
            self.par[root_x] = root_y # 低いroot_xにroot_yを繋げ、低い方が根なのでひく
            self.w[root_x] = weight - self.w[x] + self.w[y]
        else:
            self.par[root_y] = root_x # 逆
            self.w[root_y] = -weight + self.w[x] - self.w[y]
            if self.rank[root_x] == self.rank[root_y]:
                self.rank[root_x] += 1

    def same(self, x, y):
        #xとyが同じ集合に属するか
        return self.root(x) == self.root(y)

    def diff(self, x, y):
        if self.same(x, y):
            return self.w[x] - self.w[y]
        else:
            return "?"

def querying(queries, uft):
    for query in queries:
        if query[0] == 0:#unite
            uft.relate(query[1], query[2], query[3])
        else:
            print(uft.diff(query[1], query[2]))

if __name__ == '__main__':
    # https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/all/DSL_1_B
    n, q = map(int, input().split())
    queries = [list(map(int, input().split())) for i in range(q)]
    uft = WeightedUnionFindTree(n)#instant UnionFindTree
    querying(queries, uft)#Querying

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.buffer.readline

n,q= map(int,readline().split())


class WeightedUnionFind:
    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
        else:
            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)
        # xの木の高さ < yの木の高さ
        if self.rank[rx] < self.rank[ry]:
            self.par[rx] = ry
            self.weight[rx] = w - self.weight[x] + self.weight[y]
        # xの木の高さ ≧ 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)

    # xからyへのコスト
    def diff(self, x, y):
        return self.weight[x] - self.weight[y]

uf = WeightedUnionFind(n)

for i in range(q):
    s = readline().rstrip().decode('utf-8')
    if s[0] == "0":
        com,a,b,w = map(int,s.split())
    else:
        com,a,b = map(int,s.split())
    if com:
        if uf.same(a,b):
            print(uf.diff(a,b))
        else:
            print("?")
    else:
        uf.union(a,b,w)

Submission status: Accepted

Solution code:
class WeightedUnionFindTree:

    def __init__(self, n_nodes):
        super().__init__()
        self.par = [i for i in range(n_nodes)]
        self.rank = [0] * n_nodes
        self.weights = [0] * n_nodes

    def find(self, x):
        if self.par[x] == x:
            return x
        root = self.find(self.par[x])
        self.weights[x] += self.weights[self.par[x]]
        self.par[x] = root
        return root

    def unite(self, x, y, weight=0):
        root_x, root_y = self.find(x), self.find(y)
        if root_x == root_y:
            return
        if self.rank[root_x] < self.rank[root_y]:
            self.par[root_x] = root_y
            self.weights[root_x] = weight - self.weights[x] + self.weights[y]
        else:
            self.par[root_y] = root_x
            self.weights[root_y] = - \
                (weight - self.weights[x] + self.weights[y])
            if self.rank[root_x] == self.rank[root_y]:
                self.rank[root_x] += 1

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

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


if __name__ == "__main__":
    N, Q = map(int, input().split())
    uft = WeightedUnionFindTree(N)
    ans = []
    for _ in range(Q):
        type_, u, v, *weight = map(int, input().split())
        if type_ == 0:
            uft.unite(u, v, weight[0])
        else:
            ans.append(uft.diff(u, v) if uft.is_same(u, v) else '?')
    for a in ans:
        print(a)

Submission status: Accepted

Solution code:
#!python3

import sys
sys.setrecursionlimit(1000000000)
iim = lambda: map(int, input().rstrip().split())

def resolve():
    N, Q = iim()
    S = [i for i in range(N)]
    W = [0] * N
    R = [0] * N

    def find(x):
        if S[x] == x:
            return x

        i = find(S[x])
        W[x] += W[S[x]]
        S[x] = i
        return i

    def relate(x, y, w):
        i = find(x)
        j = find(y)

        if R[i] < R[j]:
            S[i] = j
            W[i] = w - W[x] + W[y]
        else:
            S[j] = i
            W[j] = -w - W[y] + W[x]
            if R[i] == R[j]:
                R[i] += 1

    def diff(x, y):
        i = find(x)
        j = find(y)

        if i != j: return "?"

        return W[x] - W[y]

    ans = []
    for com, *xyz in (map(int, s.split()) for s in sys.stdin):
        if com == 0:
            relate(*xyz)
        else:
            ans.append(diff(*xyz))
    print(*ans, sep="\n")

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
class WeightedUnionFind:
    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
        else:
            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)
        # xの木の高さ < yの木の高さ
        if self.rank[rx] < self.rank[ry]:
            self.par[rx] = ry
            self.weight[rx] = w - self.weight[x] + self.weight[y]
        # xの木の高さ ≧ 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)

    # xからyへのコスト
    def diff(self, x, y):
        if self.find(x) != self.find(y):
            return "?"
        return self.weight[x] - self.weight[y]


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

tree = WeightedUnionFind(n)

for i in range(q):
    query = list(map(int, input().split()))
    if query[0] == 0:
        x, y, z = query[1:4]
        tree.union(x, y, z)
    else:
        x, y = query[1:3]
        ans = tree.diff(x, y)
        print(ans)

Submission status: Accepted

Solution code:
class WeightedUnionFind():
    def __init__(self,n):
        self.n = n
        self.parents = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.weight = [0 for _ in range(n)]
    def find(self,x):
        root = x
        stack = [root]
        while self.parents[root] != root:
            root = self.parents[root]
            stack.append(root)
        while stack:
            s = stack.pop()
            self.weight[s] += self.weight[self.parents[s]]
        while self.parents[x] != root:
            parent = self.parents[x]
            self.parents[x] = root
            x = parent
        return root
    def unite(self,x,y,w):
        xroot = self.find(x)
        yroot = self.find(y)
        if xroot == yroot:
            return
        xrank = self.rank[xroot]
        yrank = self.rank[yroot]
        if xrank < yrank:
            self.parents[xroot] = yroot
            self.weight[xroot] = w-self.weight[x]+self.weight[y]
        else:
            self.parents[yroot] = xroot
            self.weight[yroot] = -w+self.weight[x]-self.weight[y]
            if xrank == yrank:
                self.rank[xroot] += 1

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

N,Q = map(int,input().split())
uf = WeightedUnionFind(N)
ans = []

for _ in range(Q):
    q = list(map(int,input().split()))
    if q[0] == 0:
        uf.unite(q[1],q[2],q[3])
    else:
        if uf.find(q[1]) == uf.find(q[2]):
            ans.append(uf.diff(q[1],q[2]))
        else:
            ans.append('?')

print('\n'.join(map(str,ans)))

Submission status: Accepted

Solution code:
# see: https://twitter.com/maspy_stars/status/1179226257982185472
import sys
input = sys.stdin.buffer.readline


class WeightedUnionFindTree:
    """Disjoint-Set Data Structure with weight

    complexity:
        - init: O(n)
        - find, unite, same: O(alpha(n))
    """

    def __init__(self, n_nodes):
        self.par = [i for i in range(n_nodes)]  # parent
        self.rank = [0] * n_nodes  # depth of tree
        self.weights = [0] * n_nodes

    def find(self, x):
        if self.par[x] == x:
            return x
        root = self.find(self.par[x])
        self.weights[x] += self.weights[self.par[x]]
        self.par[x] = root
        return root

    def unite(self, x, y, weight=0):
        root_x, root_y = self.find(x), self.find(y)
        if root_x == root_y:
            return
        if self.rank[root_x] < self.rank[root_y]:
            self.par[root_x] = root_y
            self.weights[root_x] = weight - self.weights[x] + self.weights[y]
        else:
            self.par[root_y] = root_x
            self.weights[root_y] = -weight - self.weights[y] + self.weights[x]
            if self.rank[root_x] == self.rank[root_y]:
                self.rank[root_x] += 1

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

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


def aoj():
    # https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/all/DSL_1_B
    N, Q = map(int, input().split())
    uft = WeightedUnionFindTree(N)
    ans = []
    for _ in range(Q):
        type_, u, v, *weight = map(int, input().split())
        if type_ == 0:
            uft.unite(u, v, weight[0])
        else:
            ans.append(uft.diff(u, v) if uft.is_same(u, v) else '?')
    print('\n'.join(map(str, ans)))


if __name__ == '__main__':
    aoj()

Submission status: Accepted

Solution code:
class WUnionFind:
    MAX_N = 0
    PAR  = [] 
    RANK = []
    DIFF_WEIGHT=[]

    def __init__(self,n):
        self.MAX_N = n
        self.PAR = [ i for i in range(n)]
        self.RANK= [ 0 ] * n
        self.DIFF_WEIGHT=[ 0 ] * n

    def root(self,x):
        if self.PAR[x] == x:
            return x
        else:
            r = self.root(self.PAR[x])
            self.DIFF_WEIGHT[x] += self.DIFF_WEIGHT[self.PAR[x]]
            self.PAR[x] = r
            return r
    
    def weight(self,x):
        self.root(x)
        return self.DIFF_WEIGHT[x]

    def issame(self,x,y):
        return self.root(x) == self.root(y)

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

    def merge(self,x,y,w):
        w += self.weight(x)
        w -= self.weight(y)
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False
        if self.RANK[x] < self.RANK[y]:
            x,y = y,x
            w = -w
        if self.RANK[x] == self.RANK[y]:
            self.RANK[x] += 1

        self.PAR[y] = x
        self.DIFF_WEIGHT[y] = w
        return True


N,Q  = map(int,input().split())
Ans = []
tree = WUnionFind(N+1)

for _ in range(Q):
    s = list(map(int,input().split()))
    if s[0] == 0:
        x = s[1]
        y = s[2]
        w = s[3]
        tree.merge(x,y,w)
    else:
        x = s[1]
        y = s[2]
        if tree.issame(x,y):
            a = tree.diff(x,y)
        else:
            a = '?'
        Ans.append(a)

for a in Ans:
    print(a)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def root(x):
    if par[x] == x:
        return x
    else:
        r = root(par[x])
        weight[x] += weight[par[x]]
        par[x] = r
        return r

def union(x,y,w):
    rx = root(x)
    ry = root(y)
    if rank[rx] < rank[ry]:
        par[rx] = ry
        weight[rx] = w - weight[x] + weight[y]
    else:
        par[ry] = rx
        weight[ry] = - w - weight[y] + weight[x]
        if rank[rx] == rank[ry]:
            rank[rx] += 1
def same(x,y):
    return root(x) == root(y)

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

n,q = LI()
par = [i for i in range(n)]
weight = [0]*n
rank = [0]*n
for _ in range(q):
    lst = LI()
    if lst[0] == 0:
        x,y,z = lst[1:4]
        if not same(x,y):
            union(x,y,z)
    else:
        x,y = lst[1:3]
        if not same(x,y):
            print('?')
        else:
            print(diff(x,y))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
input = sys.stdin.readline

def diff(node_a, node_b):
    root_a, cost_a = node_a.root(0)
    root_b, cost_b = node_b.root(0)
    if root_a == root_b:
        return True, cost_a - cost_b
    else:
        return False, cost_a - cost_b

def merge(node_a, node_b, weight):
    root_a, cost_a = node_a.root(0)
    root_b, cost_b = node_b.root(0)
    root_a.weight = weight + cost_b - cost_a
    root_a.is_root = False
    root_a.parent = root_b

class Node:
    def __init__(self):
        self.is_root = True
        self.parent = None
        self.weight = 0
    
    def root(self, cost):
        if self.is_root:
            return self, cost
        root, max_ = self.parent.root(cost + self.weight)
        self.parent = root
        self.weight = max_ - cost
        return root, max_

def main():
    n, q = map(int, input().split())
    
    nodes = [Node() for i in range(n)]

    for i in range(q):
        query = list(map(int, input().split()))
        if query[0] == 0:
            x, y, z = query[1:]
            if not diff(nodes[x], nodes[y])[0]:
                merge(nodes[x], nodes[y], z)
        else:
            x, y = query[1:]
            jud, ans = diff(nodes[x], nodes[y])
            if jud:
                print(ans)
            else:
                print("?")

if __name__ == "__main__":
    main()