Problem:


Problem F: Never Wait for Weights

In a laboratory, an assistant, Nathan Wada, is measuring weight differences between sample pieces pair by pair. He is using a balance because it can more precisely measure the weight difference between two samples than a spring scale when the samples have nearly the same weight.

He is occasionally asked the weight differences between pairs of samples. He can or cannot answer based on measurement results already obtained.

Since he is accumulating a massive amount of measurement data, it is now not easy for him to promptly tell the weight differences. Nathan asks you to develop a program that records measurement results and automatically tells the weight differences.

Input

The input consists of multiple datasets. The first line of a dataset contains two integers N and M. N denotes the number of sample pieces (2 ≤ N ≤ 100,000). Each sample is assigned a unique number from 1 to N as an identifier. The rest of the dataset consists of M lines (1 ≤ M ≤ 100,000), each of which corresponds to either a measurement result or an inquiry. They are given in chronological order.

A measurement result has the format,

    ! a b w

which represents the sample piece numbered b is heavier than one numbered a by w micrograms (a &ne; b). That is, w = wb &minus; wa, where wa and wb are the weights of a and b, respectively. Here, w is a non-negative integer not exceeding 1,000,000.

You may assume that all measurements are exact and consistent. 

An inquiry has the format,

    ? a b

which asks the weight difference between the sample pieces numbered a and b (a &ne; b).

The last dataset is followed by a line consisting of two zeros separated by a space.

Output

For each inquiry, ? a b, print the weight difference in micrograms between the sample pieces numbered a and b, wb &minus; wa, followed by a newline if the weight difference can be computed based on the measurement results prior to the inquiry. The difference can be zero, or negative as well as positive. You can assume that its absolute value is at most 1,000,000. If the difference cannot be computed based on the measurement results prior to the inquiry, print UNKNOWN followed by a newline.

Sample Input

2 2
! 1 2 1
? 1 2
2 2
! 1 2 1
? 2 1
4 7
! 1 2 100
? 2 3
! 2 3 100
? 2 3
? 1 3
! 4 3 150
? 4 1
0 0

Output for the Sample Input

1
-1
UNKNOWN
100
200
-50



Sample input:
2 2
! 1 2 1
? 1 2
2 2
! 1 2 1
? 2 1
4 7
! 1 2 100
? 2 3
! 2 3 100
? 2 3
? 1 3
! 4 3 150
? 4 1
0 0


Sample output:
1
-1
UNKNOWN
100
200
-50

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
def root(x):
    if x == parent[x]:
        return x
    y = root(parent[x])
    relative[x] += relative[parent[x]]
    parent[x] = y
    return y
def unite(a, b, w):
    pa = root(a); pb = root(b)
    if pa < pb:
        parent[pb] = pa
        relative[pb] = relative[a] + w
    else:
        parent[pa] = pb
        relative[pa] = relative[b] - w
while 1:
    N, M = map(int, input().split())
    if N == M == 0:
        break
    *parent, = range(N+1)
    relative = [0]*(N+1)
    for i in range(M):
        cmd = input().split()
        if cmd[0] == '!':
            a, b, w = map(int, cmd[1:])
            unite(a-1, b-1, w)
        else:
            a, b = map(int, cmd[1:])
            if root(a-1) != root(b-1):
                print("UNKNOWN")
            else:
                print(relative[b-1] - relative[a-1])

Submission status: Wrong Answer

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:
            self.weight[x] += self.weight[self.par[x]]
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 重さの検索
    def weighting(self, x):
        self.find(x)
        return self.weight[x]

    # 併合
    def union(self, x, y, w):
        w -= self.weighting(x)
        w += self.weighting(y)
        x = self.find(x)
        y = self.find(y)

        if self.rank[x] < self.rank[y]:
            self.weight[x] = w
            self.par[x] = y

        else:
            w = -w
            self.weight[y] = w
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

    # 各頂点間の絶対距離
    def diff(self, x, y):
        return self.weighting(x) - self.weighting(y)


N, M = 1, 1

while True:
    N, M = map(int, input().split())
    if (N == 0) & (M == 0):
        quit()
    info = [list(input().split()) for i in range(M)]
    wuf = WeightedUnionFind(N)
    for i in range(M):
        if info[i][0] == "!":
            wuf.union(int(info[i][1]), int(info[i][2]), int(info[i][3]))
        else:
            if wuf.same(int(info[i][1]), int(info[i][2])):
                print(wuf.diff(int(info[i][1]), int(info[i][2])))
            else:
                print("UNKNOWN")

Submission status: Wrong Answer

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 weighting(self, x):
        self.find(x)
        return self.weight[x]

    # 併合
    def union(self, x, y, w):
        px = self.find(x)
        py = self.find(y)
        if px != py:
            if self.rank[px] < self.rank[py]:
                self.par[px] = py
                self.weight[px] = w - self.weighting(x) + self.weighting(y)
            else:
                self.par[py] = px
                self.weight[py] = -w - self.weighting(y) + self.weighting(x)
                if self.rank[px] == self.rank[py]:
                    self.rank[px] += 1

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

    # 各頂点間の絶対距離
    def diff(self, x, y):
        return self.weighting(x) - self.weighting(y)

N, M = 1, 1

while True:
    N, M = map(int, input().split())
    if (N == 0) & (M == 0):
        quit()
    info = [list(input().split()) for i in range(M)]
    wuf = WeightedUnionFind(N)
    for i in range(M):
        if info[i][0] == "!":
            wuf.union(int(info[i][1]), int(info[i][2]), int(info[i][3]))
            #print("parent:", wuf.par)
            #print("weight:", wuf.weight)
            #print("rank:", wuf.rank, "\n")
        else:
            if wuf.same(int(info[i][1]), int(info[i][2])):
                print(wuf.diff(int(info[i][1]), int(info[i][2])))
                #print("parent:", wuf.par)
                #print("weight:", wuf.weight)
                #print("rank:", wuf.rank, "\n")
            else:
                print("UNKNOWN")
                #print("parent:", wuf.par)
                #print("weight:", wuf.weight)
                #print("rank:", wuf.rank, "\n")

Submission status: Wrong Answer

Solution code:
def solve():
    def measurement(a, b, w):
        a_root = root[a]
        b_root = root[b]
        if a_root != b_root:
            a_member = member[a]
            b_member = member[b]
            offset = w - (weight[b] - weight[a])
            if len(a_member) > len(b_member):
                a_member.extend(b_member)
                for n in b_member:
                    root[n] = a_root
                    weight[n] += offset
            else:
                b_member.extend(a_member)
                for n in a_member:
                    root[n] = b_root
                    weight[n] -= offset
    
    def inquiry(a, b):
        if root[a] == root[b]:
            return weight[b] - weight[a]
        else:
            return 'UNKNOWN'
                    
    import sys
    file_input = sys.stdin
    
    while True:
        N, M = map(int, file_input.readline().split())
        if N == 0:
            break
        
        root = [i for i in range(N + 1)]
        member = [[i] for i in range(N + 1)]
        weight = [0] * (N + 1)
        
        for _ in range(M):
            line = file_input.readline()
            if line[0] == '!':
                a, b, w = map(int, line[2:].split())
                measurement(a, b, w)
            else:
                a, b= map(int, line[2:].split())
                print(inquiry(a, b))

solve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
def root(x):
    if x == parent[x]:
        return x
    y = root(parent[x])
    relative[x] += relative[parent[x]]
    parent[x] = y
    return y
def unite(a, b, w):
    pa = root(a); pb = root(b)
    pw = relative[a] + w - relative[b]
    if pa < pb:
        parent[pb] = pa
        relative[pb] = pw
    else:
        parent[pa] = pb
        relative[pa] = -pw
while 1:
    N, M = map(int, input().split())
    if N == M == 0:
        break
    *parent, = range(N)
    relative = [0]*N
    for i in range(M):
        cmd = input().split()
        if cmd[0] == '!':
            a, b, w = map(int, cmd[1:])
            unite(a-1, b-1, w)
        else:
            a, b = map(int, cmd[1:])
            if root(a-1) != root(b-1):
                print("UNKNOWN")
            else:
                print(relative[b-1] - relative[a-1])

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 weighting(self, x):
        self.find(x)
        return self.weight[x]

    # 併合
    def union(self, x, y, w):
        px = self.find(x)
        py = self.find(y)
        if px != py:
            if self.rank[px] < self.rank[py]:
                self.par[px] = py
                self.weight[px] = w - self.weight[x] + self.weight[y]
            else:
                self.par[py] = px
                self.weight[py] = -w - self.weight[y] + self.weight[x]
                if self.rank[px] == self.rank[py]:
                    self.rank[px] += 1

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

    # 各頂点間の絶対距離
    def diff(self, x, y):
        return self.weight[x] - self.weight[y]

N, M = 1, 1

while True:
    N, M = map(int, input().split())
    if (N == 0) & (M == 0):
        quit()
    info = [list(input().split()) for i in range(M)]
    wuf = WeightedUnionFind(N)
    for i in range(M):
        if info[i][0] == "!":
            wuf.union(int(info[i][1]), int(info[i][2]), int(info[i][3]))
            #print("parent:", wuf.par)
            #print("weight:", wuf.weight)
            #print("rank:", wuf.rank, "\n")
        else:
            if wuf.same(int(info[i][1]), int(info[i][2])):
                print(wuf.diff(int(info[i][1]), int(info[i][2])))
                #print("parent:", wuf.par)
                #print("weight:", wuf.weight)
                #print("rank:", wuf.rank, "\n")
            else:
                print("UNKNOWN")
                #print("parent:", wuf.par)
                #print("weight:", wuf.weight)
                #print("rank:", wuf.rank, "\n")

Submission status: Accepted

Solution code:
def solve():
    def measurement(a, b, w):
        a_root = root[a]
        b_root = root[b]
        if a_root != b_root:
            a_member = member[a_root]
            b_member = member[b_root]
            offset = w - (weight[b] - weight[a])
            if len(a_member) > len(b_member):
                a_member.extend(b_member)
                for n in b_member:
                    root[n] = a_root
                    weight[n] += offset
            else:
                b_member.extend(a_member)
                for n in a_member:
                    root[n] = b_root
                    weight[n] -= offset
    
    def inquiry(a, b):
        if root[a] == root[b]:
            return weight[b] - weight[a]
        else:
            return 'UNKNOWN'
                    
    import sys
    file_input = sys.stdin
    
    while True:
        N, M = map(int, file_input.readline().split())
        if N == 0:
            break
        
        root = [i for i in range(N + 1)]
        member = [[i] for i in range(N + 1)]
        weight = [0] * (N + 1)
        
        for _ in range(M):
            line = file_input.readline()
            if line[0] == '!':
                a, b, w = map(int, line[2:].split())
                measurement(a, b, w)
            else:
                a, b= map(int, line[2:].split())
                print(inquiry(a, b))

solve()

Submission status: Accepted

Solution code:
def solve():
    def measurement(a, b, w):
        a_root = root[a]
        b_root = root[b]
        if a_root != b_root:
            a_member = member[a_root]
            b_member = member[b_root]
            offset = w - (weight[b] - weight[a])
            if len(a_member) > len(b_member):
                a_member.extend(b_member)
                for n in b_member:
                    root[n] = a_root
                    weight[n] += offset
            else:
                b_member.extend(a_member)
                for n in a_member:
                    root[n] = b_root
                    weight[n] -= offset
    
    def inquiry(a, b):
        if root[a] == root[b]:
            return weight[b] - weight[a]
        else:
            return 'UNKNOWN'
                    
    import sys
    file_input = sys.stdin.readlines()
    
    while True:
        N, M = map(int, file_input[0].split())
        if N == 0:
            break
        
        root = [i for i in range(N + 1)]
        member = [[i] for i in range(N + 1)]
        weight = [0] * (N + 1)
        
        for line in file_input[1:M+1]:
            if line[0] == '!':
                a, b, w = map(int, line[2:].split())
                measurement(a, b, w)
            else:
                a, b= map(int, line[2:].split())
                print(inquiry(a, b))
        
        del file_input[:M+1]

solve()

Submission status: Accepted

Solution code:
def solve():
    def measurement(a, b, w):
        a_root = root[a]
        b_root = root[b]
        if a_root != b_root:
            a_member = member[a_root]
            b_member = member[b_root]
            offset = w - (weight[b] - weight[a])
            if len(a_member) > len(b_member):
                a_member.extend(b_member)
                for n in b_member:
                    root[n] = a_root
                    weight[n] += offset
            else:
                b_member.extend(a_member)
                for n in a_member:
                    root[n] = b_root
                    weight[n] -= offset
    
    def inquiry(a, b):
        if root[a] == root[b]:
            return weight[b] - weight[a]
        else:
            return 'UNKNOWN'
    
    def operation(line):
        if line[0] == '!':
            a, b, w = map(int, line[2:].split())
            measurement(a, b, w)
        else:
            a, b = map(int, line[2:].split())
            return inquiry(a, b)
    
    import sys
    file_input = sys.stdin.readlines()
    
    while True:
        N, M = map(int, file_input[0].split())
        if N == 0:
            break
        
        root = [i for i in range(N + 1)]
        member = [[i] for i in range(N + 1)]
        weight = [0] * (N + 1)
        
        ans = (operation(line) for line in file_input[1:M+1])
        ans = filter(lambda x: x != None, ans)
        print(*ans, sep='\n')
        
        del file_input[:M+1]

solve()

Submission status: Accepted

Solution code:
def solve():
    def measurement(a, b, w):
        a_root = root[a]
        b_root = root[b]
        if a_root != b_root:
            a_member = member[a_root]
            b_member = member[b_root]
            offset = w - (weight[b] - weight[a])
            if len(a_member) > len(b_member):
                a_member.extend(b_member)
                for n in b_member:
                    root[n] = a_root
                    weight[n] += offset
            else:
                b_member.extend(a_member)
                for n in a_member:
                    root[n] = b_root
                    weight[n] -= offset
     
    def inquiry(a, b):
        if root[a] == root[b]:
            return weight[b] - weight[a]
        else:
            return 'UNKNOWN'
                     
    import sys
    file_input = sys.stdin.readlines()
    ans = []
     
    while True:
        N, M = map(int, file_input[0].split())
        if N == 0:
            break
         
        root = [i for i in range(N + 1)]
        member = [[i] for i in range(N + 1)]
        weight = [0] * (N + 1)
         
        for line in file_input[1:M+1]:
            if line[0] == '!':
                a, b, w = map(int, line[2:].split())
                measurement(a, b, w)
            else:
                a, b= map(int, line[2:].split())
                ans.append(inquiry(a, b))
         
        del file_input[:M+1]
    
    print(*ans, sep='\n')
 
solve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 5)

# 連結性の確認
class UnionFind():
    def __init__(self, n):
        self.parents = list(range(n))
        self.weight = [0] * n
        self.rank = [0] * n

    def find(self, a):
        if self.parents[a] == a:
            return a
        p = self.find(self.parents[a])
        self.weight[a] += self.weight[self.parents[a]]
        self.parents[a] = p
        return p

    def union(self, a, b, w):
        self.find(a), self.find(b)
        w += self.weight[a]
        w -= self.weight[b]
        a = self.find(a)
        b = self.find(b)

        if a == b: return

        if self.rank[a] < self.rank[b]:
            self.parents[a] = b
            self.weight[a] = -w
        else:
            self.parents[b] = a
            self.weight[b] = w
            if self.rank[a] == self.rank[b]:
                self.rank[a] += 1

    def weight_check(self, a, b):
        self.find(a), self.find(b)
        return - self.weight[a] + self.weight[b]

while True:
    N, M = map(int, input().split())
    if not(N | M):
        break

    uf = UnionFind(N)
    for i in range(M):
        input_str = input().split()
        if input_str[0] == '!':
            a, b, w = map(int, input_str[1:])
            uf.union(a - 1, b - 1, w)

        else:
            a, b = map(lambda x: int(x) - 1, input_str[1:])
            if uf.find(a) != uf.find(b):
                print('UNKNOWN')
                continue
            print(uf.weight_check(a, b))

Submission status: Accepted

Solution code:

import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

class WeightedUnionFind():

    def __init__(self,N):
        self.N = N
        self.parents = [-1] * self.N
        self.diff_weight = [0] * self.N
    
    def find(self,x):
        if self.parents[x] < 0:
            return x
        else:
            p = self.find(self.parents[x])
            self.diff_weight[x] += self.diff_weight[self.parents[x]]
            self.parents[x] = p
            return p
    
    def weight(self,x):#xの親からの重みを返す
        self.find(x)
        return self.diff_weight[x]
    
    def diff(self,x,y):#同じグループにいたらxとyの重みの差を返す
        if self.find(x) == self.find(y):
            return self.weight(y) - self.weight(x)
        else:
            return 10000000000

    def unite(self,x,y,w):#wieght(y) = weight(x) + dとなるように合体
        w += self.weight(x)
        w -= self.weight(y)

        x = self.find(x)
        y = self.find(y)
        if x == y:
            if self.diff(x,y) == w:
                return True
            else:
                return False

        if self.parents[x] > self.parents[y]:
            x,y = y,x
            w *= -1
        self.parents[x] += self.parents[y]
        self.parents[y] = x
        self.diff_weight[y] = w
        return True
    
    def same(self,x,y):
        return self.find(x) == self.find(y)
        
    def size(self,x):
        return -self.parents[self.find(x)]

def solve(N,M):
    uf = WeightedUnionFind(N)
    for _ in range(M):
        q = input().split()
        if q[0] == '!':
            a,b,w = map(int,q[1:])
            a -= 1
            b -= 1
            uf.unite(a,b,w)
        else:
            a,b = map(int,q[1:])
            a -= 1
            b -= 1
            ans = uf.diff(a,b)
            if ans == 10000000000:
                print('UNKNOWN')
            else:
                print(ans)

def main():
    while True:
        N,M = map(int,input().split())
        if N == 0 and M == 0:
            break
        solve(N,M)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# Author: cr4zjh0bp
# Created: Fri Mar 20 22:48:43 UTC 2020
import sys
 
stdin = sys.stdin
inf = 1 << 60
mod = 1000000007
 
ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

class WUnionFind:
    def __init__(self, n, sum_unity=0):
        self.n = n
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.diff_weight = [sum_unity for _ in range(n)]
        self._size = [1 for _ in range(n)]
        self._edges = 0

    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            r = self.find(self.par[x])
            self.diff_weight[x] += self.diff_weight[self.par[x]]
            self.par[x] = r
            return r
        
    def unite(self, x, y, w):
        w += self.weight(x)
        w -= self.weight(y)
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.diff_weight[x] = -w
            self._size[y] += self._size[x]
            self._edges += 1
        else:
            self.par[y] = x
            self.diff_weight[y] = w
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self._size[x] += self._size[y]
            self._edges += 1

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

    def diff(self, x, y):
        return self.weight(y) - self.weight(x)
    
    def size(self, x):
        x = self.find(x)
        return self._size[x]
    
    def trees(self):
        return self.n - self._edges

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

while True:
    n, m = na()
    if n == 0 and m == 0:
        break
    wuf = WUnionFind(n)
    for i in range(m):
        que = nas()
        if que[0] == '!':
            a, b, w = list(map(int, que[1:]))
            a -= 1
            b -= 1
            wuf.unite(a, b, w)
        elif que[0] == '?':
            a, b = list(map(int, que[1:]))
            a -= 1
            b -= 1
            if wuf.same(a, b):
                print(wuf.diff(a, b))
            else:
                print("UNKNOWN")

Submission status: Accepted

Solution code:
class Value_UnionFind():

    def __init__(self,n):
        self.par = [i for i in range(n)]
        self.differ_weight = [0] * n
        self.rank = [0] * n

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

    def weight(self, x):
        self.root(x)
        return self.differ_weight[x]

    def unit(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, w = y, x, -w
        if self.rank[x] == self.rank[y]: self.rank[x] += 1
        self.par[y] = x
        self.differ_weight[y] = w
        return True

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

def main(n, m):
    Union = Value_UnionFind(n)
    for _ in range(m):
        x = list(map(str, input().split()))
        q = x[0]
        if q == "!":
            a, b, w = map(int, x[1:])
            Union.unit(a-1, b-1, w)
        if q == "?":
            a, b = map(int,x[1:])
            if Union.root(a-1) != Union.root(b-1):
                print("UNKNOWN")
            else:
                print(Union.differ(a-1, b-1))



while 1:
    n, m = map(int, input().split())
    if n == m == 0:
        break
    main(n,m)

Submission status: Accepted

Solution code:
class PotUnionFind:
    def __init__(self, n):
        self.parent = list(range(n)) #親ノード
        self.size = [1]*n #グループの要素数
        self.diff_p = [0]*n #親ノードを基準としたポテンシャル
 
    def root(self, x): #root(x): xの根ノードを返す．
        while self.parent[x] != x:
            self.diff_p[x] += self.diff_p[self.parent[x]]
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x 

    def weight(self, x): #root(x): xの根ノードを返す．
        c=0
        while self.parent[x] != x:
            self.diff_p[x] += self.diff_p[self.parent[x]]
            self.parent[x] = self.parent[self.parent[x]]
            c += self.diff_p[x]
            x = self.parent[x]
        return c


    def merge(self, x, y, dxy): #ポテンシャル差p(y)-p(x)=dxyでxとyの組をまとめる
        dxy += self.weight(x) - self.weight(y) #dxyをで置き換え
        x,y = self.root(x), self.root(y)
        if x == y: return False
        if self.size[x] < self.size[y]: #xの要素数が大きいように
            x,y,dxy = y,x,-dxy
        self.size[x] += self.size[y] #xの要素数を更新
        self.parent[y] = x #yをxにつなぐ
        self.diff_p[y] = dxy #yの相対ポテンシャルを更新
        return True
 
    def issame(self, x, y): #xとyが同じ組ならTrue
        return self.root(x) == self.root(y)
        
    def diff(self,x,y): #xを基準としたyのポテンシャルを返す 
        if self.root(x) == self.root(y):
            return self.weight(y) - self.weight(x)
        else:
            return None

    def getsize(self,x): #xのいるグループの要素数を返す
        return self.size[self.root(x)]


import sys
while True:
    n,Q=[int(i) for i in input().split()]
    if n==0 and Q ==0: exit()
    T=PotUnionFind(n)
    for _ in [0]*(Q):
        u = [i for i in sys.stdin.readline().split()]
        if u[0] =="!":
            u1, u2, u3 = int(u[1])-1, int(u[2])-1, int(u[3])
            T.merge(u1,u2,u3)
        else:
            u1, u2 = int(u[1])-1, int(u[2])-1
            if T.issame(u1,u2):
                print(T.diff(u1,u2))
            else:
                print("UNKNOWN")

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**13
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

class UnionFind:
    def __init__(self, size):
        self.table = [-1 for _ in range(size)]

    def find(self, x):
        if self.table[x] < 0:
            return x
        else:
            self.table[x] = self.find(self.table[x])
            return self.table[x]

    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] <= self.table[s2]:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return True
        return False

    def subsetall(self):
        a = []
        for i in range(len(self.table)):
            if self.table[i] < 0:
                a.append((i, -self.table[i]))
        return a

def main():
    random.seed(42)
    rr = []

    def f(n, m):
        qa = [LS() for _ in range(m)]
        d = collections.defaultdict(lambda: collections.defaultdict(int))
        for i in range(n+1):
            d[i][i] = random.randrange(1,100)
        r = []
        uf = UnionFind(n+1)
        for q in qa:
            if q[0] == '!':
                a,b,w = map(int, q[1:])
                fa = uf.find(a)
                fb = uf.find(b)
                if fa == fb:
                    continue
                uf.union(a,b)
                # print('a,b',a,b)
                # print('dfa', d[fa])
                # print('dfb', d[fb])
                if fa == uf.find(a):
                    sa = w + (d[fa][a] - d[fb][b])
                    for k in d[fb].keys():
                        d[fa][k] = d[fb][k] + sa
                else:
                    sa = (d[fa][a] - d[fb][b]) + w
                    for k in d[fa].keys():
                        d[fb][k] = d[fa][k] - sa
                # print('sa',sa)
                # print('dfa', d[fa])
                # print('dfb', d[fb])
            else:
                a,b = map(int , q[1:])
                fa = uf.find(a)
                if fa != uf.find(b):
                    r.append('UNKNOWN')
                else:
                    r.append(d[fa][b] - d[fa][a])
        # for k in d.keys():
        #     print('k,d',k,d[k])

        return r

    while 1:
        n,m = LI()
        if n == 0 and m == 0:
            break
        rr.extend(f(n,m))

    return '\n'.join(map(str,rr))


print(main())