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:
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())
U=WeightedUnionFind(n)
def C(U):
    for i in range(m):
        l, r, d = map(int, input().split())
        if U.same(l-1, r-1):
            if U.diff(l-1, r-1)!=d:
                return False
        else:
            U.union(l-1, r-1, d)
    return True
if C(U):
    print('Yes')
else:
    print('No')

Submission status: Accepted

Solution code:
#ABC087-D
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(input())
def S(): return list(input())

class WeightedUnionFind:
    def __init__(self, size):
        """
        :param collections.Iterable nodes:
        """
        self._parents = [i for i in range(size)]
        self._ranks = [0 for _ in range(size)]
        self._sizes = [1 for _ in range(size)]
        # 直近の親からの重み。root なら 0
        self._weights = [0 for _ in range(size)]
 
    def unite(self, x, y, w):
        """
        x が属する木と y が属する木を併合
        :param x:
        :param y:
        :param w: x と y の重みの差; (重み y) - (重み x)
        :return:
        """
        rx = self.find(x)
        ry = self.find(y)
        if rx == ry:
            return
 
        # rank が小さい方が下
        if self._ranks[rx] > self._ranks[ry]:
            # x が root
            self._parents[ry] = rx
            self._sizes[rx] += self._sizes[ry]
            # root 間の重みに変換
            self._weights[ry] = w + self._weights[x] - self._weights[y]
        else:
            # y が root
            self._parents[rx] = ry
            self._sizes[ry] += self._sizes[rx]
            # root 間の重みに変換
            self._weights[rx] = -w + self._weights[y] - self._weights[x]
            if self._ranks[rx] == self._ranks[ry]:
                self._ranks[ry] += 1
 
    def find(self, x):
        """
        x が属する木の root
        :param x:
        :return:
        """
        if self._parents[x] == x:
            return x
        root = self.find(self._parents[x])
        self._weights[x] += self._weights[self._parents[x]]
        self._parents[x] = root
        return root
 
    def size(self, x):
        """
        x が属する木のノード数
        :param x:
        :return:
        """
        return self._sizes[self.find(x)]
 
    def weight(self, x):
        """
        :param x:
        :return:
        """
        # 経路圧縮
        self.find(x)
        return self._weights[x]
 
    def diff(self, x, y):
        """
        (y の重み) - (x の重み)
        :param x:
        :param y:
        :return:
        """
        if self.find(x) == self.find(y):
            return self._weights[y] - self._weights[x]
        return float('inf')
    
    def is_same(self,x,y):
        if self.find(x) == self.find(y):
            return True
        else:
            return False
        
n,m=IL()
UF=WeightedUnionFind(n)
for i in range(m):
    l,r,d=IL()
    if UF.is_same(l-1,r-1) and UF.diff(l-1,r-1)!=d:
        print("No")
        break
    UF.unite(l-1,r-1,d)
else:
    print("Yes")

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10000)
INF = float('inf')


class WeightedUnionFind:
    def __init__(self, size):
        """
        :param collections.Iterable nodes:
        """
        self._parents = [i for i in range(size)]
        self._ranks = [0 for _ in range(size)]
        self._sizes = [1 for _ in range(size)]
        # 直近の親からの重み。root なら 0
        self._weights = [0 for _ in range(size)]

    def unite(self, x, y, w):
        """
        x が属する木と y が属する木を併合
        :param x:
        :param y:
        :param w: x と y の重みの差; (重み y) - (重み x)
        :return:
        """
        rx = self.find(x)
        ry = self.find(y)
        if rx == ry:
            return

        # rank が小さい方が下
        if self._ranks[rx] > self._ranks[ry]:
            # x が root
            self._parents[ry] = rx
            self._sizes[rx] += self._sizes[ry]
            # root 間の重みに変換
            self._weights[ry] = w + self._weights[x] - self._weights[y]
        else:
            # y が root
            self._parents[rx] = ry
            self._sizes[ry] += self._sizes[rx]
            # root 間の重みに変換
            self._weights[rx] = -w + self._weights[y] - self._weights[x]
            if self._ranks[rx] == self._ranks[ry]:
                self._ranks[ry] += 1

    def find(self, x):
        """
        x が属する木の root
        :param x:
        :return:
        """
        if self._parents[x] == x:
            return x
        root = self.find(self._parents[x])
        self._weights[x] += self._weights[self._parents[x]]
        self._parents[x] = root
        return root

    def size(self, x):
        """
        x が属する木のノード数
        :param x:
        :return:
        """
        return self._sizes[self.find(x)]

    def weight(self, x):
        """
        :param x:
        :return:
        """
        # 経路圧縮
        self.find(x)
        return self._weights[x]

    def diff(self, x, y):
        """
        (y の重み) - (x の重み)
        :param x:
        :param y:
        :return:
        """
        if self.find(x) == self.find(y):
            return self._weights[y] - self._weights[x]
        return float('inf')


N, M = list(map(int, input().split()))

uf = WeightedUnionFind(N + 1)

ok = True
for _ in range(M):
    l, r, d = list(map(int, input().split()))
    if uf.find(l) == uf.find(r) and uf.diff(l, r) != d:
        ok = False
        break
    uf.unite(l, r, d)

if ok:
    print('Yes')
else:
    print('No')

Submission status: Accepted

Solution code:
import sys
import time

sys.setrecursionlimit(10000)
INF = float('inf')


class WeightedUnionFind:
    def __init__(self, nodes):
        """
        :param collections.Iterable nodes:
        """
        self._parents = {k: k for k in nodes}
        self._ranks = {k: 0 for k in nodes}
        self._sizes = {k: 1 for k in nodes}
        # 直近の親からの重み。root なら 0
        self._weights = {k: 0 for k in nodes}

    def unite(self, x, y, w):
        """
        x が属する木と y が属する木を併合
        :param x:
        :param y:
        :param w: x と y の重みの差; (重み y) - (重み x)
        :return:
        """
        rx = self.find(x)
        ry = self.find(y)
        if rx == ry:
            return

        # rank が小さい方が下
        if self._ranks[rx] > self._ranks[ry]:
            # x が root
            self._parents[ry] = rx
            self._sizes[rx] += self._sizes[ry]
            # root 間の重みに変換
            self._weights[ry] = w + self._weights[x] - self._weights[y]
        else:
            # y が root
            self._parents[rx] = ry
            self._sizes[ry] += self._sizes[rx]
            # root 間の重みに変換
            self._weights[rx] = -w + self._weights[y] - self._weights[x]
            if self._ranks[rx] == self._ranks[ry]:
                self._ranks[ry] += 1

    def find(self, x):
        """
        x が属する木の root
        :param x:
        :return:
        """
        if self._parents[x] == x:
            return x
        root = self.find(self._parents[x])
        self._weights[x] += self._weights[self._parents[x]]
        self._parents[x] = root
        return root

    def size(self, x):
        """
        x が属する木のノード数
        :param x:
        :return:
        """
        return self._sizes[self.find(x)]

    def weight(self, x):
        """
        :param x:
        :return:
        """
        # 経路圧縮
        self.find(x)
        return self._weights[x]

    def diff(self, x, y):
        """
        (y の重み) - (x の重み)
        :param x:
        :param y:
        :return:
        """
        if self.find(x) == self.find(y):
            return self._weights[y] - self._weights[x]
        return float('inf')


N, M = list(map(int, input().split()))

uf = WeightedUnionFind([i + 1 for i in range(N)])

ok = True
for _ in range(M):
    l, r, d = list(map(int, input().split()))
    if uf.find(l) == uf.find(r) and uf.diff(l, r) != d:
        ok = False
        break
    uf.unite(l, r, d)

if ok:
    print('Yes')
else:
    print('No')

Submission status: Accepted

Solution code:
queue=[]
N,M=map(int,input().split())
NE=9223372036854775807
mp=[NE]*(N+1)
lst=[[] for _ in range(N+1)]
for _ in range(M):
    L,R,D = map(int, input().split())
    lst[L].append((L,R,D))
    lst[R].append((L,R,D))

def check(L, R, D):
    if mp[L] == NE:
        mp[L] = mp[R]-D
    elif mp[R] == NE:
        mp[R] = mp[L]+D
    else:
        if mp[L]+D != mp[R]:
            print("No")
            exit()

def check_list(ls, checking):
    while len(ls):
        L,R,D = ls.pop()
        check(L,R,D)
        nx = R if L == checking else L
        if len(lst[nx]): queue.append(nx)

for i in range(1, N+1):
    if mp[i] == NE: mp[i] = 0
    check_list(lst[i], i)

    while(len(queue) > 0):
        num = queue.pop()
        check_list(lst[num], num)
print("Yes")

Submission status: Accepted

Solution code:
queue=[]
N,M=map(int,input().split())
NE=9223372036854775807
mp=[NE]*(N+1)
lst=[[] for _ in range(N+1)]
for _ in range(M):
    L,R,D = map(int, input().split())
    lst[L].append((L,R,D))
    lst[R].append((L,R,D))

def check(L, R, D):
    if mp[L] == NE:
        mp[L] = mp[R]-D
    elif mp[R] == NE:
        mp[R] = mp[L]+D
    else:
        if mp[L]+D != mp[R]:
            print("No")
            exit()

def check_list(ls, checking):
    while len(ls):
        L,R,D = ls.pop()
        check(L,R,D)
        nx = R if L == checking else L
        if len(lst[nx]): queue.append(nx)

for i in range(1, N+1):
    if mp[i] == NE: mp[i] = 0
    check_list(lst[i], i)

    while(len(queue) > 0):
        num = queue.pop()
        check_list(lst[num], num)
print("Yes")

Submission status: Accepted

Solution code:
queue=[]
N,M=map(int,input().split())
NE=9223372036854775807
mp=[NE]*(N+1)
lst=[[] for _ in range(N+1)]
for _ in range(M):
    L,R,D = map(int, input().split())
    lst[L].append((L,R,D))
    lst[R].append((L,R,D))

isinit = True
def check(L, R, D):
    if mp[L] == NE and mp[R] == NE:
        return 1
    elif mp[L] == NE:
        mp[L] = mp[R]-D
    elif mp[R] == NE:
        mp[R] = mp[L]+D
    else:
        if mp[L]+D != mp[R]:
            print("No")
            exit()

def check_list(ls, checking):
    while len(ls):
        L,R,D = ls.pop()
        if L == checking:
            check(L,R,D)
            if len(lst[R]):
                queue.append(R)
        else:
            check(L,R,D)
            if len(lst[L]):
                queue.append(L)

# print(lst)
for i in range(1, N+1):
    if mp[i] == NE: mp[i] = 0
    check_list(lst[i], i)

    while(len(queue) > 0):
        num = queue.pop()
        check_list(lst[num], num)
# print(mp)
print("Yes")

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
LRD = [(lambda x: [int(x[0])-1,int(x[1])-1,int(x[2])])(input().split()) for _ in [0]*M]

connect = [[] for _ in range(N)]
for L,R,D in LRD:
    connect[L].append([R,D])
    connect[R].append([L,-D])

ans = True
n = [None] * N
n0 = 0
while ans:
    q = [n0]
    n[n0] = 0
    for i in q:
        for j,d in connect[i]:
            if n[j] == None:
                n[j] = n[i] + d
                q.append(j)
            elif n[j]-n[i] != d:
                ans = False
                break
        if not ans:
            break
    for i in range(n0,N):
        if n[i] == None:
            n0 = i
            break
    else:
        break

if ans:
    print("Yes")
else:
    print("No")

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1145141919)

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

path=[[] for _ in range(N+1)]

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

cost=[None for _ in range(N+1)]

def walk(i, c):
	if cost[i] is None:
		cost[i] = c
		for j,d in path[i]:
			if not walk(j, c+d):
				return False
	return cost[i] == c

ans = "Yes"

for i in range(1, N+1):
	if cost[i] is None and not walk(i, 0):
		ans = "No"
		break

print(ans)

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 unite(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 = map(int, input().split())
graph = WeightedUnionFind(N)

for i in range(M):
    l, r, d = map(int, input().split())
    if not graph.same(l-1, r-1):
        graph.unite(l-1, r-1, d)
    else:
        if graph.diff(l-1, r-1) != d:
            print('No')
            quit()

print('Yes')

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 unite(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 = map(int, input().split())
graph = WeightedUnionFind(N)

for i in range(M):
    l, r, d = map(int, input().split())
    if not graph.same(l-1, r-1):
        graph.unite(l-1, r-1, d)
    else:
        if graph.diff(l-1, r-1) != d:
            print('No')
            quit()

print('Yes')

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
INF = 10 ** 9
N ,M = map(int,input().split())

G = [[] for i in range(N+1)]

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

dp = [INF] * (N+1)

def dfs(l):
    for r, d in G[l]:
        if dp[r] == INF:
            dp[r] = dp[l] + d
            if not dfs(r):
                return False
        elif dp[r] != dp[l] + d:
            return False
    return True

for i in range(1, N+1):
    if dp[i] == INF:
        dp[i] = 0
        if not dfs(i):
            print('No')
            exit()

print('Yes')

Submission status: Accepted

Solution code:
N, M = list(map(int, input().split()))
LRD = [list(map(int, input().split())) for _ in range(M)]

roots = [(i,0) for i in range(N+1)] #(root, distance_from_i_to_root)

def find_root(a, roots=roots):
  if roots[a][0] == a:
    return (a,0)
  else:
    r, d = find_root(roots[a][0])
    roots[a] = (r, roots[a][1] + d)
  return roots[a]

def unite(l, r, d, roots=roots):
  root_l, d_l = find_root(l)
  root_r, d_r = find_root(r)
  if root_l == root_r:
    if d_l == d + d_r:
      return True
    else:
      return False
  else:
    roots[root_l] = (root_r, d + d_r - d_l)
    return True

for l,r,d in LRD:
  if not unite(l,r,d):
    print('No')
    break
else:
  print('Yes')

Submission status: Accepted

Solution code:
N, M = list(map(int, input().split()))
LRD = [list(map(int, input().split())) for _ in range(M)]

roots = [(i,0) for i in range(N+1)] #(root, distance_to_root)

def find_root(a, roots=roots):
  if roots[a][0] == a:
    return (a,0)
  else:
    r, d = find_root(roots[a][0])
    roots[a] = (r, roots[a][1] + d)
  return roots[a]

def unite(l, r, d, roots=roots):
  root_l, d_l = find_root(l)
  root_r, d_r = find_root(r)
  if root_l == root_r:
    if d_l == d + d_r:
      return True
    else:
      return False
  else:
    roots[root_l] = (r, d - d_l)
    return True

for l,r,d in LRD:
  if not unite(l,r,d):
    print('No')
    break
else:
  print('Yes')

Submission status: Accepted

Solution code:
class UnionFindTree:
    def __init__(self, size):
        self.parent = list(range(size))
        self.dist = [0] * size
 
    def find_root(self, x):
        if self.parent[x] == x:
            return x, 0
        else:
            self.parent[x], d = self.find_root(self.parent[x])
            self.dist[x] += d
            return self.parent[x], self.dist[x]
 
    def union(self, x, y, d):
        r1, d1 = self.find_root(x)
        r2, d2 = self.find_root(y)
        if r1 != r2:
            self.parent[r2] = r1
            self.dist[r2] = (d1 - d2) + d
        else:
            if (d2 - d1) != d:
                return False
        return True
import sys
import math
stdin = sys.stdin
 
ni = lambda: int(ns())
na = lambda: list(map(int, input().split()))
ns = lambda: input()

def main():
    N,M = na()
    tree = UnionFindTree(N+1)
    for i in range(M):
        l,r,d = na()
        if(not tree.union(l,r,d)):
            print("No")
            return
        
    print("Yes")

main()

Submission status: Accepted

Solution code:
from collections import deque


n,m = map(int,input().split())
tree = [[] for i in range(n)]
for i in range(m):
    tmp1, tmp2, cost = map(int, input().split())
    tmp1 -= 1
    tmp2 -= 1
    tree[tmp1].append([tmp2, cost])
    tree[tmp2].append([tmp1, -cost])

is_visited = [False]*n
pos = [0]*n
for i in range(n):
    if is_visited[i]:
        continue
    else:
        is_visited[i] = True
        q = deque()
        q.append(i)
        while q:
            here = q.popleft()
            for next, cost in tree[here]:
                if is_visited[next]:
                    if pos[next] != pos[here] + cost:
                        print("No")
                        exit()
                else:
                    is_visited[next] = True
                    pos[next] = pos[here] + cost
                    q.append(next)
print("Yes")

Submission status: Accepted

Solution code:
from collections import deque
N,M = map(int,input().split())
edge = [[] for i in range(N)]
x = [float('inf')]*N
for i in range(M):
  L,R,D = map(int,input().split())
  edge[L-1].append([R-1,D])
  edge[R-1].append([L-1,-D])
for i in range(N):
  if x[i] == float('inf'):
    x[i] = 0
    q = deque([i])
    while len(q) > 0:
      now = q.popleft()
      for e in edge[now]:
        if x[e[0]] == float('inf'):
          x[e[0]] = x[now]+e[1]
          q.append(e[0])
        elif x[e[0]]-x[now] != e[1]:
          print('No')
          exit()
print('Yes')

Submission status: Accepted

Solution code:
import queue

n, m = [int(i) for i in input().split(" ")]

g = [[] for i in range(0, n + 1)]
v = [0] * (n + 1)
v_asn = [False] * (n + 1)
f = True

for i in range(0, m):
    l, r, d = [int(i) for i in input().split(" ")]
    g[l].append([r, d])
    g[r].append([l, -d])

for i in range(1, n + 1):
    if not v_asn[i]:
        q = queue.Queue()
        v_asn[i] = True
        q.put(i)
        while not q.empty():
            qi = q.get()
            for a in g[qi]:
                if not v_asn[a[0]]:
                    v_asn[a[0]] = True
                    v[a[0]] = v[qi] + a[1]
                    q.put(a[0])
                else:
                    if v[a[0]] != v[qi] + a[1]:
                        f = False
                        break
        if not f:
            break

if f:
    print("Yes")
else:
    print("No")

Submission status: Accepted

Solution code:
def main():
    N, M = map(int, input().split())
    G = [[] for _ in range(N)]
    D = [-1 for _ in range(N)]
    E = [0 for _ in range(N)]
    for _ in range(M):
        l, r, d = map(int, input().split())
        G[l - 1].append((r - 1, d))
        E[r - 1] = 1
    for i in range(N):
        if E[i] == 1:
            continue
        s = [i]
        while len(s) > 0:
            ll = s.pop()
            for rr, dd in G[ll]:
                if D[rr] == -1:
                    D[rr] = D[ll] + dd
                    s.append(rr)
    for l in range(N):
        for r, d in G[l]:
            if D[l] + d != D[r]:
                print('No')
                return
    print('Yes')


main()

Submission status: Accepted

Solution code:
import sys

class UnionFind:
    def __init__(self, n):
        self.root = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        self.size = [1] * (n+1)  # The number of nodes under the target node.
        self.weight = [0] * (n+1)  # Distance from the root

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

    def unite(self, x, y, w=0):
        rx = self.find(x)
        ry = self.find(y)
        if self.rank[rx] < self.rank[ry]:
            self.root[rx] = ry
            self.size[ry] += self.size[rx]
            self.weight[rx] = w - self.weight[x] + self.weight[y]
        else:
            self.root[ry] = rx
            self.size[rx] += self.size[ry]
            self.weight[ry] = -w - self.weight[y] + self.weight[x]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def is_same(self, x, y):
        return self.find(x) == self.find(y)
    
    def diff(self, x, y):
        return self.weight[y] - self.weight[x]


def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    UF = UnionFind(N)

    for _ in range(M):
        l, r, d = map(int, input().split())
        l -= 1
        r -= 1

        if not UF.is_same(l, r):
            UF.unite(l, r, d)

        elif UF.is_same(l, r) and UF.diff(r, l) != d:
            return 'No'

        else:
            continue

    return 'Yes'


if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:
n, m = [int(item) for item in input().split()]
lrd = [[int(item) for item in input().split()] for _ in range(m)]

class DisjointSet:
  def __init__(self, n):
    self.par = [i for i in range(n+1)]
    self.dist = [0] * (n+1)
    self.rank = [0] * (n+1)

  def find(self, x):
    if self.par[x] == x:
      return x
    else:
      y = self.find(self.par[x])
      self.dist[x] += self.dist[self.par[x]]
      self.par[x] = y
      return self.par[x]
    
  def union(self, x, y, d):
    dx = self.dist[x]
    dy = self.dist[y]
    x = self.find(x)
    y = self.find(y)
    if self.rank[x] < self.rank[y]:
      self.par[x] = y      
      self.dist[x] = d + dy - dx
    else:
      self.par[y] = x
      self.dist[y] = -d - dy + dx
      if self.rank[x] == self.rank[y]:
        self.rank[x] += 1
        
  def issame(self, x, y):
    return self.find(x) == self.find(y)
  
  def diff(self, x, y):
    return self.dist[x] - self.dist[y]

harmony = True
djs = DisjointSet(n)
for l, r, d in lrd:
  if djs.issame(l,r):
    if djs.diff(l,r) != d:
      harmony = False
  else:
    djs.union(l,r,d)
    
if harmony:
  print("Yes")
else:
  print("No")

Submission status: Accepted

Solution code:
import sys

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

    def root(self, x:int)->int:
        """根を求める"""
        if self.par[x] == x: # if root
            return x
        else:
            root_x = self.root(self.par[x]) # 経路圧縮
            self.weight[x] += self.weight[self.par[x]]
            self.par[x] = root_x
            return root_x

    def get_weight(self, x: int)->int:
        """x の重みを取得"""
        self.root(x) # 経路圧縮
        return self.weight[x]

    def get_diff(self, x:int, y:int)->int:
        """x と y の差分を取得"""
        if not self.is_same(x, y): return "?" # 判定不可
        return self.get_weight(y) - self.get_weight(x)

    def is_same(self, x:int, y:int)->bool:
        """x と y が同じ集合に属するか否か"""
        return self.root(x)==self.root(y)

    def unite(self, x:int, y:int, w:int)->bool:
        """weight[y] = weight[x]+w となるようにmerge(x が y の親)
        return True if merge 可能"""
        if self.is_same(x, y): return False
        root_x = self.root(x)
        root_y = self.root(y)
        w += (self.weight[x] - self.weight[y]) # 重みを補正
        if self.rank[root_x] < self.rank[root_y]:
            self.par[root_x] = root_y
            self.weight[root_x] = -w
        else:
            self.par[root_y] = root_x
            self.weight[root_y] = w
            if self.rank[root_x] == self.rank[root_y]:
                self.rank[root_x] += 1
        return True

    def get_size(self, x:int)->int:
        """xの属するグループのサイズ"""
        return self.size[self.root(x)]

if __name__ == "__main__":
    N,Q = map(int, sys.stdin.readline().split())
    wuf = WeightedUnionFind(N)
    for _ in range(Q):
        l,r,d = map(lambda x: int(x)-1, sys.stdin.readline().split())
        d += 1
        if not wuf.unite(l,r,d):
            if wuf.get_diff(l,r)!=d:
                print("No")
                sys.exit()
    print("Yes")

Submission status: Accepted

Solution code:
N, M = list(map(int, input().split()))
LRD = [list(map(int, input().split())) for _ in range(M)]

def rootT(x):
  if T[x][0] == -1:
    return x, 0
  else:
    k, d = rootT(T[x][0])
    T[x][1] += d
    T[x][0] = k
    return k, T[x][1]

T = [[-1, 0] for _ in range(N + 1)]

Ans = "Yes"
for L, R, D in LRD:
  l, ld = rootT(L)
  r, rd = rootT(R)
  if l == r:
    if ld + D != rd:
      Ans = "No"
      break
  else:
    x = D + ld - rd
    if x < 0:
      x *= -1
      l, r = (r, l)
    T[r] = [l, x]

print(Ans)

Submission status: Accepted

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

    def root(self, x):
        if self.par[x] == x:
            return x
        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 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

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

def solve():
    N,M=map(int,input().split())
    uf = UnionFind(N)
    for i in range(M):
        l,r,d=map(int,input().split())
        if uf.issame(l,r):
            if uf.diff(l,r) != d:
                return 'No'
        else:
            uf.merge(l,r,d)
    return 'Yes'

print(solve())