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

Solution (Python):
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
    

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])
            
            
        elif(query[0]==1):
            res = diff(weighted_union_find_tree,query[1],query[2])
            print(res)

Solution (Python):


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("?")

Solution (Python):
import sys

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

    def root(self, x:int)->int:
        """根を求める"""
        if self.par[x] == x: 
            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: 
            print(wuf.get_diff(*x))

Solution (Python):
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')

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



Group=[[i,0] for i in range(n)]

def find(x):
    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):  
    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])
        
    else:
        if find(query[1])[0]==find(query[2])[0]:
            print(find(query[2])[1]-find(query[1])[1])
        else:
            print("?")

Solution (Python):
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")