Problem:


Score : 400 points

Problem Statement

There are N people standing on the x-axis.
Let the coordinate of Person i be x_i.
For every i, x_i is an integer between 0 and 10^9 (inclusive).
It is possible that more than one person is standing at the same coordinate.

You will given M pieces of information regarding the positions of these people.
The i-th piece of information has the form (L_i, R_i, D_i).
This means that Person R_i is to the right of Person L_i by D_i units of distance, that is, x_{R_i} - x_{L_i} = D_i holds.

It turns out that some of these M pieces of information may be incorrect.
Determine if there exists a set of values (x_1, x_2, ..., x_N) that is consistent with the given pieces of information.

Constraints

1 \leq N \leq 100 000

0 \leq M \leq 200 000

1 \leq L_i, R_i \leq N (1 \leq i \leq M)

0 \leq D_i \leq 10 000 (1 \leq i \leq M)

L_i \neq R_i (1 \leq i \leq M)

If i \neq j, then (L_i, R_i) \neq (L_j, R_j) and (L_i, R_i) \neq (R_j, L_j).

D_i are integers.

Input

Input is given from Standard Input in the following format:

N M
L_1 R_1 D_1
L_2 R_2 D_2
:
L_M R_M D_M

Output

If there exists a set of values (x_1, x_2, ..., x_N) that is consistent with all given pieces of information, print Yes; if it does not exist, print No.

Sample Input 1

3 3
1 2 1
2 3 1
1 3 2

Sample Output 1

Yes

Some possible sets of values (x_1, x_2, x_3) are (0, 1, 2) and (101, 102, 103).

Sample Input 2

3 3
1 2 1
2 3 1
1 3 5

Sample Output 2

No

If the first two pieces of information are correct, x_3 - x_1 = 2 holds, which is contradictory to the last piece of information.

Sample Input 3

4 3
2 1 1
2 3 5
3 4 2

Sample Output 3

Yes

Sample Input 4

10 3
8 7 100
7 9 100
9 8 100

Sample Output 4

No

Sample Input 5

100 0

Sample Output 5

Yes



Sample input:
3 3
1 2 1
2 3 1
1 3 2


Sample output:
Yes

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
from collections import deque, Counter
def getN():
    return int(input())
def getList():
    return list(map(int, input().split()))
import math
INF = 10**10
def bfs(graph, visited, position, root):
    visited[root] = 1
    position[root] = 0
    deq = deque([root])
    while(deq):
        cur = deq.pop()
        # print(cur)
        for nxt, dist in graph[cur]:
            if position[cur] + dist != position[nxt]:
                if position[nxt] != INF:
                    return False
                else:
                    position[nxt] = position[cur] + dist
            if not visited[nxt]:
                deq.append(nxt)
                visited[nxt] = 1

    return True

def main():
    n,m = getList()
    position = [INF for i in range(n)]
    graph = [[] for i in range(n)]
    for i in range(m):
        a,b,c = getList()
        graph[a-1].append((b-1, c))
        graph[b - 1].append((a-1, -c))

    # print(graph)
    visited = [0 for i in range(n)]
    for i in range(n):
        if not visited[i]:
            # print("===========")
            res = bfs(graph, visited, position, i)
            if res == False:
                print("No")
                return

    print("Yes")

if __name__ == "__main__":

    main()

Submission status: Accepted

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

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

def diff(u, v):
    return weight(v) - weight(u)

def unite(u, v, w):
    w += diff(v, u)
    u = root(u)
    v = root(v)
    if u == v:
        return
    if rank[u] < rank[v]:
        u, v = v, u
        w = -w
    par[v] = u
    diff_weight[v] = w
    if rank[u] == rank[v]:
        rank[u] += 1

def same(u, v):
    return root(u) == root(v)

N, M = map(int, input().split())
par = list(range(N))
rank = [0] * N
diff_weight = [0] * N
for _ in range(M):
    l, r, d = map(int, input().split())
    l -= 1
    r -= 1
    if same(l, r):
        dist = diff(l, r)
        if dist != d:
            print("No")
            exit()
    else:
        unite(l, r, d)

print("Yes")

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

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]

def chk(a,b,c):
    return True if uf.diff(a,b) == c else False
n,m = inpl()
z = [-1] * n
uf = WeightedUnionFind(n)
for i in range(m):
    a,b,c = inpl()
    a -= 1; b -= 1
    if uf.same(a,b):
        if not chk(a,b,c):
            print('No')
            quit()
    else:
        uf.union(a,b,c)
print('Yes')

Submission status: Accepted

Solution code:
vs = set()
from collections import defaultdict
def dfs_w(d, stack):
    depthh = defaultdict(int)
    path = [0]
    pvs = set()
    if stack[0] in vs:
        return True
    while stack:
        v, dpd = stack.pop()
        if v > 0:
            parent = path[-1]
            path.append(v)
            vs.add(v)
            pvs.add(v)
            depthh[v] = depthh[parent] + dpd

            for u, dpd in d[v]:
                if u in pvs:
                    if depthh[u] != depthh[v] + dpd:
                        return False
                if u in vs:
                    continue
                stack += [(-v, dpd), (u, dpd)]
        else:
            path.pop()

    return True
#    return S, F, depth, depthh

if __name__ == '__main__':
    N, M = map(int, input().split())
    G = [set() for _ in range(N+1)]
    for _ in range(M):
        a, b, c = map(int, input().split())
        G[a].add((b,c))
        G[b].add((a,-c))
    for i in range(N):
        if i in vs:
            continue
        stack = [(i+1, 0)] 
        r =  dfs_w(G, stack)
        if not r:
            break
    if r:
        print("Yes")
    else:
        print("No")

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
vs = set()
def dfs_w(d, stack):
    depth = defaultdict(int)
    pvs = set()
    while stack:
        v = stack.pop()
        vs.add(v)
        pvs.add(v)
        for u, dpd in d[v]:
            if u in pvs:
                if depth[u] != depth[v] + dpd:
                    return False
            if u in vs:
                continue
            depth[u] = depth[v] + dpd
            stack.append(u)
    return True

if __name__ == '__main__':
    from collections import defaultdict
    N, M = map(int, input().split())
    G = defaultdict(set)
    for _ in range(M):
        a, b, c = map(int, input().split())
        G[a].add((b,c))
        G[b].add((a,-c))
    for i in range(N):
        if i+1 in vs:
            continue
        stack = [i+1] 
        r =  dfs_w(G, stack)
        if not r:
            break
    if r:
        print("Yes")
    else:
        print("No")

Submission status: Accepted

Solution code:
from collections import deque
import sys
input = sys.stdin.readline

def bfs(graph, start):
    while graph != {}:
        start = min(graph.keys())
        queue = deque([])
        queue.append(start)
        pos = {}
        pos[start] = 0
        while queue:
            u = queue.popleft()
            for v,d in graph[u].items():
                if v not in pos:
                    pos[v] = pos[u] + d
                    if v in graph:
                        queue.append(v)
                elif pos[v] != pos[u] + d:
                    return False
            del graph[u]
            # print(queue)
    return True

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

graph = {}
for i in range(m):
    l,r,d = map(int, input().split())
    if l not in graph:
        graph[l] = {}
    graph[l][r] = d
    if r not in graph:
        graph[r] = {}
    graph[r][l] = -d

if m == 0 or bfs(graph, min(graph.keys())):
    print('Yes')
else:
    print('No')
# print(graph)

Submission status: Accepted

Solution code:
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]


N, M = map(int, input().split())
uft = WeightedUnionFindTree(N)

for _ in range(M):
    l, r, d = map(int, input().split())
    l, r = l-1, r-1
    if not uft.is_same(l, r):
        uft.unite(l, r, d)
    else:
        if uft.diff(l, r) != d:
            print("No")
            quit()
else:
    print("Yes")

Submission status: Accepted

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

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

    def union(self, x, y, w):
        w = w + self.weight(x) - self.weight(y)
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            self.parents[y] += self.parents[x]
            self.parents[x] = y
            self.par_weight[x] = -w
        else:
            self.parents[x] += self.parents[y]
            self.parents[y] = x
            self.par_weight[y] = w

    def weight(self, x):
        if self.parents[x] < 0:
            return 0
        else:
            return self.par_weight[x] + self.weight(self.parents[x])

    def diff(self, x, y):
        if self.find(x) != self.find(y):
            raise Exception('"{}" belongs to a different tree from "{}"'.format(x, y))
        return self.weight(y) - self.weight(x)


N, M = map(int, input().split())
uf = WeightedUnionFind(N)
for i in range(M):
    L, R, D = map(int, input().split())
    L -= 1
    R -= 1
    if uf.find(L) == uf.find(R):
        if uf.diff(L, R) != D:
            res = 'No'
            break
    else:
        uf.union(L, R, D)
else:
    res = 'Yes'

print(res)

Submission status: Accepted

Solution code:
import sys
from collections import deque
input = sys.stdin.buffer.readline

N, M = map(int, input().split())
adj = [[] for _ in range(N+1)]
for _ in range(M):
    l, r, d = map(int, input().split())
    adj[l].append((r, d))
    adj[r].append((l, -d))

seen = ['!'] * (N+1)
for i in range(1, N+1):
    if seen[i] == '!':
        que = deque()
        seen[i] = 0
        que.append(i)
        while que:
            v = que.popleft()
            for u, d in adj[v]:
                if seen[u] == '!':
                    seen[u] = seen[v] + d
                    que.append(u)
                else:
                    if seen[v] + d != seen[u]:
                        print('No')
                        exit()
print('Yes')

Submission status: Accepted

Solution code:
class UnionFind():
    # 作りたい要素数nで初期化
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)

    # ノードxのrootノードを見つける
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    
    # 木の併合、入力は併合したい各ノード
    def Unite(self, x, y):
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        if(x == y):
            return 
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    # ノードxが属する木のサイズ
    def Count(self, x):
        return -self.root[self.Find_Root(x)]

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
graph = [[] for _ in range(N)]
uni = UnionFind(N)
for _ in range(M):
    a, b, d = map(int, input().split())
    uni.Unite(a-1, b-1)
    graph[a-1].append((d, b-1))
    graph[b-1].append((-d, a-1))

INF = 10**14
A = [INF]*N
def bfs(start):
    q = [start]
    A[start] = 0
    while q:
        qq = []
        for p in q:
            for d, np in graph[p]:
                if A[np] == INF:
                    A[np] = A[p] + d
                    qq.append(np)
                elif A[np] != A[p]+d:
                    return False
        q = qq
    return True

root = set()
for i in range(N):
    root.add(uni.Find_Root(i))

ok = True
for r in root:
    ok = ok and bfs(r)

print("Yes" if ok else "No")

Submission status: Accepted

Solution code:
class WeightedUnionFind():
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0 for i in range(n)]
        self.diff_weight = [0 for i in range(n)]

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

    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 unite(self, x, y, w):
        # y の root をくっつけるので。
        w += self.weight(x); w -= self.weight(y)
        x = self.find(x); y = self.find(y)
        if x == y:
            return False
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            w = -w
            self.diff_weight[x] = w
        elif self.rank[y] < self.rank[x]:
            self.par[y] = x
            self.diff_weight[y] = w
        else:
            self.par[y] = x
            self.diff_weight[y] = w
            self.rank[x] += 1
        return True

N, M = map(int, input().split())
wuf = WeightedUnionFind(N)
for i in range(M):
    l, r, d = map(int, input().split())
    l-=1;r-=1
    if wuf.find(l) == wuf.find(r):
        if wuf.diff(l, r) != d:
            print('No')
            break
    wuf.unite(l, r, d)
else:
    print('Yes')

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline


class WeightedUnionFind:
    def __init__(self, N):
        self.par = [i for i in range(N)]
        self.rank = [0] * N
        self.weight = [0] * N  # 親までの距離

    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            r = self.find(self.par[x])
            self.weight[x] += self.weight[self.par[x]]
            self.par[x] = r
            return r

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


def main():
    N, M = map(int, readline().split())
    m = map(int, read().split())
    LRD = list(zip(m, m, m))

    D = WeightedUnionFind(N)

    a = []
    for l, r, d in LRD:
        l -= 1
        r -= 1
        D.union(l, r, d)
        a.append(l)
        a.append(r)

    for i in set(a):
        D.find(i)

    for l, r, d in LRD:
        l -= 1
        r -= 1
        if d != D.diff_w(l, r):
            print('No')
            sys.exit()

    print('Yes')


main()

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline


class WeightedUnionFind:
    def __init__(self, N):
        self.par = [i for i in range(N)]
        self.rank = [0] * N
        self.weight = [0] * N  # 親までの距離

    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            r = self.find(self.par[x])
            self.weight[x] += self.weight[self.par[x]]
            self.par[x] = r
            return r

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


def main():
    N, M = map(int, readline().split())
    m = map(int, read().split())
    LRD = list(zip(m, m, m))

    D = WeightedUnionFind(N)

    for l, r, d in LRD:
        l -= 1
        r -= 1
        D.union(l, r, d)

    for l, r, d in LRD:
        l -= 1
        r -= 1
        D.find(l)
        D.find(r)
        if d != D.diff_w(l, r):
            print('No')
            sys.exit()

    print('Yes')


main()

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline


class WeightedUnionFind:
    def __init__(self, N):
        self.par = [i for i in range(N)]
        self.rank = [0] * N
        self.weight = [0] * N  # 親までの距離

    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            r = self.find(self.par[x])
            self.weight[x] += self.weight[self.par[x]]
            self.par[x] = r
            return r

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


def main():
    N, M = map(int, readline().split())
    m = map(int, read().split())
    LRD = list(zip(m, m, m))

    D = WeightedUnionFind(N)

    for l, r, d in LRD:
        l -= 1
        r -= 1
        D.union(l, r, d)

    for i in range(N):
        D.find(i)

    for l, r, d in LRD:
        l -= 1
        r -= 1
        if d != D.diff_w(l, r):
            print('No')
            sys.exit()
    
    print('Yes')


main()

Submission status: Accepted

Solution code:
class WeightedUnionFind():
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0 for i in range(n)]
        # 親ノードとの重み
        self.diff_weight = [0 for i in range(n)]

    def find(self, x):
        if self.par[x] == x:
            return x
        # 親ノードはまだ上書きしない
        root = self.find(self.par[x])
        self.diff_weight[x] += self.diff_weight[self.par[x]]
        self.par[x] = root
        return self.par[x]

    def weight(self, x):
        """ x 根に対する重みを返す """
        self.find(x)
        return self.diff_weight[x]

    def diff(self, x, y):
        """ x と y の差分をとる """
        return self.weight(y) - self.weight(x)

    def unite(self, x, y, w):
        """ ノード x の下にノード y をつける。辺の重みは、w """
        # ただし、実際には、x の根と y の 根をくっつけるので、補正
        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]:
            # y の下に x をつけることになるので、重さは反転させる
            self.par[x] = y
            w = -w
            self.diff_weight[x] = w
        elif self.rank[y] < self.rank[x]:
            self.par[y] = x
            self.diff_weight[y] = w
        else:
            self.par[y] = x
            self.rank[x] += 1
            self.diff_weight[y] = w

N, M = map(int, input().split())
wuf = WeightedUnionFind(N)
for i in range(M):
    l, r, d = map(int, input().split())
    l -= 1; r -= 1
    # これまでに入力されたものと等しくないか確認する
    if wuf.find(l) == wuf.find(r):
        if wuf.diff(l, r) != d:
            print('No')
            break
    else:
        wuf.unite(l, r, d)
else:
    print('Yes')

Submission status: Accepted

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

class WeightUnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        self.weight = [0] * n

    # xの根を求める
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            px = self.find(self.parents[x])
            self.weight[x] += self.weight[self.parents[x]]
            self.parents[x] = px
            return px
    
    # xの根から距離
    def dist(self, x):
        self.find(x)
        return self.weight[x]

    # w[y] = w[x] + wとなるようにxとyを併合
    def unite(self, x, y, w):
        w += self.weight[x] - self.weight[y]
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return False
        else:
            # sizeの大きいほうがx
            if self.parents[x] > self.parents[y]:
                x, y = y, x
                w = -w
            self.parents[x] += self.parents[y]
            self.parents[y] = x
            self.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 diff(self, x, y):
        return self.dist(y) - self.dist(x)


    


def main():
    N, M = map(int, input().split())
    uni = WeightUnionFind(N)
    for _ in range(M):
        L, R, D = map(int, input().split())
        L -= 1
        R -= 1
        if uni.same(L, R):
            if D != uni.diff(L, R):
                print('No')
                exit()
        else:
            uni.unite(L,R,D)

    print('Yes')
    


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
n,m=map(int,input().split())
lrd=[list(map(int,input().split())) for i in range(m)]
x=["a"]*(n+1)
#iより右にいるデータ
R=[[] for i in range(n+1)]
L=[[] for i in range(n+1)]
for u in lrd:
    l,r,d=u
    R[l].append([r,d])
    L[r].append([l,d])
for i in range(1,n+1):
    if x[i]=="a":
        x[i]=0
        que=[i]
        while que:
            h=que.pop()
            for u in R[h]:
                r,d=u
                if x[r]=="a":
                    x[r]=x[h]+d
                    que.append(r)
                else:
                    if x[r]==x[h]+d:
                        continue
                    else:
                        print("No")
                        sys.exit()
            for u in L[h]:
                l,d=u
                if x[l]=="a":
                    x[l]=x[h]-d
                    que.append(l)
                else:
                    if x[l]==x[h]-d:
                        continue
                    else:
                        print("No")
                        sys.exit()
print("Yes")

Submission status: Accepted

Solution code:
def resolve():

    N,M = map(int,input().split())
    root = list(range(N))
    depth = [1 for _ in range(N)]
    dist = [0 for _ in range(N)]

    def find(a,root,dist):
        if root[a] == a:
            return (a,0)
        else:
            root[a],d = find(root[a],root,dist)
            dist[a] += d
            return(root[a],dist[a])

    def unite(a,b,d,root,depth,dist):
        A,dist_a = find(a,root,dist)
        B,dist_b = find(b,root,dist)
        if A == B:
            if dist_b - dist_a == d:
                return True
            else:
                return False
        else:
            if depth[A] > depth[B]:
                root[B] = A
                depth[A] += depth[B]
                dist[B] = dist_a - dist_b + d
            else:
                root[A] = B
                depth[B] += depth[A]
                dist[A] = dist_b - dist_a - d
            return True
        
    ans = True
    for _ in range(M):
        L,R,D = map(int,input().split())
        if not (unite(L-1,R-1,D,root,depth,dist)):
            ans = False
            break
    print("Yes" if ans else "No")
resolve()

Submission status: Accepted

Solution code:
#設定
import sys
input = sys.stdin.buffer.readline

#ライブラリインポート
from collections import defaultdict

#入力受け取り
def getlist():
	return list(map(int, input().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)
        self.size = [1] * (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 same_check(self, x, y):
        return self.find(x) == self.find(y)

    def union(self, x, y, w):
        rx = self.find(x)
        ry = self.find(y)
        if self.rank[rx] < self.rank[ry]:
            if self.same_check(x, y) != True:
                self.size[y] += self.size[x]
                self.size[x] = 0
            self.par[rx] = ry
            self.weight[rx] = w - self.weight[x] + self.weight[y]
        else:
            if self.same_check(x, y) != True:
               self.size[x] += self.size[y]
               self.size[y] = 0
            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 size(self, x):
        x = self.find(x)
        return self.size(x)

    def diff(self, x, y):
        if self.same_check(x, y) == True:
            return self.weight[x] - self.weight[y]
        else:
            print("inf")

#処理内容
def main():
	N, M = getlist()
	judge = "Yes"
	UF = WeightedUnionFind(N)
	for i in range(M):
		L, R, D = getlist()
		if UF.same_check(L - 1, R - 1):
			if UF.diff(L - 1, R - 1) != D:
				judge = "No"
				break
		else:
			UF.union(L - 1, R - 1, D)
	print(judge)



if __name__ == '__main__':
	main()

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):
        return self.weight[x] - self.weight[y]
    
n,m=map(int,input().split())
uf=WeightedUnionFind(n)
for i in range(m):
    a,b,c=map(int,input().split())
    if not uf.same(a,b):
        uf.union(a,b,c)
    else:
        if uf.diff(a,b)!=c:
            print('No')
            exit()
print('Yes')

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**5)
class UnionFind():
  def __init__(self, n):
    self.n = n
    self.root = [-1]*(n+1)
    self.rnk = [0]*(n+1)
    self.weight = [0]*(n+1)
  def Find_Root(self, x):
    if(self.root[x] < 0):
      return x
    else:
      r = self.Find_Root(self.root[x])
      self.weight[x] += self.weight[self.root[x]]
      self.root[x] = r
      return r
  def GetWeight(self, x):
    self.Find_Root(x)
    return self.weight[x]
  def Unite(self, x, y, w):
    w += self.GetWeight(x)
    w -= self.GetWeight(y)
    x = self.Find_Root(x)
    y = self.Find_Root(y)
    if(x == y):
      return False
    if self.rnk[x] < self.rnk[y]:
      x, y = y, x
      w = -w
    if self.rnk[x] == self.rnk[y]:
      self.rnk[x] += 1
    self.root[y] = x
    self.weight[y] = w
    return True
  def isSameGroup(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.GetWeight(y) - self.GetWeight(x)
  
def main():
  N, M = map(int, input().split())
  lrd = [list(map(int, input().split())) for _ in range(M)]
  U = UnionFind(N)
  for i in range(M):
    l, r, d = lrd[i]
    if not U.isSameGroup(l, r):
      U.Unite(l, r, d)
    else:
      if U.Diff(l, r) != d:
        print('No')
        exit()
  print('Yes')
  
    
if __name__ == "__main__":
  main()