典型068

典型068.py

# 偶奇で重みをy - x = v か y - x = -v かで変えて重み付きUnionFindでクエリに答える．
# People on a Line に似ている．

class WeightedUnionFind:
    __slots__ = ("root", "diff_weight")

    def __init__(self, N):
        """root[v] = vの親, diff_weight[v] = 根からの重み"""
        N += 1
        self.root = [-1] * N
        self.diff_weight = [0] * N

    def find(self, x):
        que = []
        while self.root[x] >= 0:
            que.append(x)
            x = self.root[x]

        for i in reversed(que):
            self.diff_weight[i] += self.diff_weight[self.root[i]]
            self.root[i] = x

        return x

    def weight(self, x):
        self.find(x)
        return self.diff_weight[x]

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

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

    def union(self, x, y, w):
        """weight(y) - weight(x) = w となるように union する"""
        x_root = self.find(x)
        y_root = self.find(y)
        w += self.diff_weight[x]
        w -= self.diff_weight[y]
        x, y = x_root, y_root
        if x == y:
            return
        if self.root[y] < self.root[x]:
            x, y, w = y, x, -w
        self.root[x] += self.root[y]
        self.root[y] = x
        self.diff_weight[y] = w


import sys
input = sys.stdin.readline

n = int(input())
res = []
uf = WeightedUnionFind(n)

for _ in range(int(input())):
    t, x, y, v = map(int, input().split())
    x -= 1; y -= 1
    if t:
        if uf.same(x, y):
            k = uf.difference(y, x)
            if x % 2 == 0:
                k -= v
            else:
                k += v
            if y % 2 == 0:
                k = -k

            res.append(str(k))
        else:
            res.append("Ambiguous")
    else:
        if x % 2 == 0:
            uf.union(y, x, v)
        else:
            uf.union(y, x, -v)

print("\n".join(res))