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):
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)

Solution (Python):


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

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

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

Solution (Python):

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)]  
        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[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():
    
    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()

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

Solution (Python):


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))

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

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

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

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


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)

    
    def find_root(self,x):
        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
    
    def unite(self,x,y,w):
        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):
        return self.find_root(x)==self.find_root(y)

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


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

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

Solution (Python):

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



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


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)


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


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



"""
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:
"""













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


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


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



"""
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])
"""



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


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


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

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

Solution (Python):
class WeightedUnionFind:
    def __init__(self, N):
        
        
        self.vertices = [-1 for _ in range(N)]
        self.rank = [0] * N
        self.diff_weight = [0] * N
    
    def weight(self, v):
        self.find(v) 
        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:
            
            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) 
        s2 = self.find(v) 
        
        if s1 == s2: 
            return False
        
        if self.rank[s1] > self.rank[s2]: 
            self.vertices[s1] += self.vertices[s2] 
            self.vertices[s2] = s1
            self.diff_weight[s2] = w - self.diff_weight[v] + self.diff_weight[u]
        else: 
            self.vertices[s2] += self.vertices[s1] 
            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('?')

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

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

Solution (Python):


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