Problem:


Score : 600 points

Problem Statement

Kenkoooo found a simple connected graph.
The vertices are numbered 1 through n.
The i-th edge connects Vertex u_i and v_i, and has a fixed integer s_i.

Kenkoooo is trying to write a positive integer in each vertex so that the following condition is satisfied:

For every edge i, the sum of the positive integers written in Vertex u_i and v_i is equal to s_i.

Find the number of such ways to write positive integers in the vertices.

Constraints

2 \leq n \leq 10^5

1 \leq m \leq 10^5

1 \leq u_i < v_i \leq n

2 \leq s_i \leq 10^9

If i\neq j, then u_i \neq u_j  or v_i \neq v_j.

The graph is connected.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

n m
u_1 v_1 s_1
:
u_m v_m s_m

Output

Print the number of ways to write positive integers in the vertices so that the condition is satisfied.

Sample Input 1

3 3
1 2 3
2 3 5
1 3 4

Sample Output 1

1

The condition will be satisfied if we write 1,2 and 3 in vertices 1,2 and 3, respectively.
There is no other way to satisfy the condition, so the answer is 1.

Sample Input 2

4 3
1 2 6
2 3 7
3 4 5

Sample Output 2

3

Let a,b,c and d be the numbers to write in vertices 1,2,3 and 4, respectively.
There are three quadruples (a,b,c,d) that satisfy the condition:

(a,b,c,d)=(1,5,2,3)

(a,b,c,d)=(2,4,3,2)

(a,b,c,d)=(3,3,4,1)

Sample Input 3

8 7
1 2 1000000000
2 3 2
3 4 1000000000
4 5 2
5 6 1000000000
6 7 2
7 8 1000000000

Sample Output 3

0



Sample input:
3 3
1 2 3
2 3 5
1 3 4


Sample output:
1

Submission status: Accepted

Solution code:
from sys import stdin, stdout
from itertools import repeat
def main():
    n, m, = map(int, stdin.readline().split())
    dat = map(int, stdin.read().split(), repeat(10, 3 * m))
    la = [None] * (n + 1)
    xt = [None] * (3 * m)
    j = 0
    for i in xrange(m):
        x, y = dat[j], dat[j+1]
        xt[j] = la[y]
        la[y] = j
        j += 1
        xt[j] = la[x]
        la[x] = j
        j += 2
    st = [1]
    pu = st.append
    po = st.pop
    col = [0] * (n + 1)
    col[1] = 1
    f = None
    par = [None] * (n + 1)
    while st:
        x = po()
        y = la[x]
        while y is not None:
            z = dat[y]
            if not col[z]:
                col[z] = col[x] ^ 3
                par[z] = (x, dat[y/3*3+2])
                pu(z)
            elif col[z] == col[x] and f is None:
                f = (x, z)
                s = dat[y/3*3+2]
            y = xt[y]
    dp = [None] * (n + 1)
    if f is not None:
        px = []
        pz = []
        x, z = f
        while x != 1:
            px.append(par[x])
            x = par[x][0]
        while z != 1:
            pz.append(par[z])
            z = par[z][0]
        while px and pz and px[-1] == pz[-1]:
            px.pop()
            pz.pop()
        px += pz[::-1]
        k = [x[1] for x in px]
        s += sum(k)
        if s % 2:
            print 0
            return
        z = s / 2 - sum(k[::2])
        dp[f[1]] = z
        pu(f[1])
        while st:
            x = po()
            if dp[x] <= 0:
                print 0
                return
            y = la[x]
            while y is not None:
                z = dat[y]
                s = dat[y/3*3+2]
                if dp[z] is None:
                    dp[z] = s - dp[x]
                    pu(z)
                elif dp[z] + dp[x] != s:
                    print 0
                    return
                y = xt[y]
        print 1
        return
    pu(1)
    dp[1] = 0
    while st:
        x = po()
        y = la[x]
        while y is not None:
            z = dat[y]
            s = dat[y/3*3+2]
            if dp[z] is None:
                dp[z] = s - dp[x]
                pu(z)
            elif dp[z] + dp[x] != s:
                print 0
                return
            y = xt[y]
    x = 1 - min(dp[i] for i in xrange(1, n + 1) if col[i] == 1)
    for i in xrange(1, n + 1):
        if col[i] == 1:
            dp[i] += x
        else:
            dp[i] -= x
    x = min(dp[i] for i in xrange(1, n + 1) if col[i] == 2)
    if x <= 0:
        print 0
    else:
        print x
main()

Submission status: Accepted

Solution code:
# E
from collections import deque

n, m = map(int, input().split())
G = dict()
for i in range(1, n+1):
    G[i] = dict()
    
for _ in range(m):
    u, v, s = map(int, input().split())
    G[u][v] = s
    G[v][u] = s

case = 1

done_flg = [0]*(n+1)
res_list = [0]*(n+1)
plmi_flg = [0]*(n+1)

queue = deque([1])
done_flg[1] = 1
plmi_flg[1] = 1

dif_list = []

while len(queue) > 0:
    u = queue.popleft()
    for v in G[u].keys():
        if done_flg[v] == 0:
            done_flg[v] = 1
            res_list[v] = G[u][v] - res_list[u]
            plmi_flg[v] = -plmi_flg[u]
            queue.append(v)
        elif plmi_flg[v] == -plmi_flg[u]:
            if res_list[v] != G[u][v] - res_list[u]:
                case = 9
                break
        else:
            d = G[u][v] - res_list[u] - res_list[v]
            if d % 2 == 1:
                case = 9
                break
            else:
                dif_list.append((d // 2)*plmi_flg[u])
                case = 2
    if case == 9:
        break
            
            
# simple case
if case == 9:
    print(0)
elif case == 2:
    d = dif_list[0]
    check1 = True
    for d_ in dif_list:
        if d_ != d:
            check1 = False
    if check1 == False:
        print(0)
    else:
        for i in range(n+1):
            if plmi_flg[i]==1:
                res_list[i] += d
            elif plmi_flg[i]==-1:
                res_list[i] -= d
        if min(res_list[1:]) > 0:
            print(1)
        else:
            print(0)
elif case == 1:
    res_min_1 = min([res_list[i] for i in range(1, n+1) if plmi_flg[i]==1])
    res_min_2 = min([res_list[i] for i in range(1, n+1) if plmi_flg[i]==-1])
    r = max(0, (res_min_2 - 1) - (-res_min_1 + 1) + 1)
    print(r)

Submission status: Accepted

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys,collections,itertools,re,math,fractions,decimal,random,array,bisect,heapq

# decimal.getcontext().prec = 50
sys.setrecursionlimit(100000)
# MOD = 10**9 + 7

def solve(f):
    n, m = f.read_int_list()
    g = collections.defaultdict(list)
    g2 = {}
    for _ in xrange(m):
        u, v, s = f.read_int_list()
        g[u].append((v, s))
        g[v].append((u, s))
        if u < v:
            g2[(u,v)] = s
        else:
            g2[(v,u)] = s

    vis = [None] * (n+1)
    vis[1] = (1, 0)
    res = set()

    def dfs(v):
        for vi, si in g[v]:
            if vis[vi] is not None:
                if v > vi:
                    res.add((vi,v))
                else:
                    res.add((v,vi))
            else:
                vis[vi] = (vis[v][0]*-1, si-vis[v][1])
                dfs(vi)

    dfs(1)

    a = None
    for u, v in res:
        aa = vis[u][0]+vis[v][0]
        if aa == 0:
            if g2[(u,v)] != vis[u][1] + vis[v][1]: return 0
        else:
            bb = g2[(u,v)]-vis[u][1]-vis[v][1]
            a2 = bb / aa
            if aa*a2 != bb: return 0
            if a is not None and a != a2: return 0
            a = a2

    a1min = a2min = float('inf')
    a1max = a2max = -float('inf')
    for i in xrange(1,n+1):
        if vis[i][0] == 1:
            a1min = min(vis[i][1], a1min)
            a1max = max(vis[i][1], a1max)
        else:
            a2min = min(vis[i][1], a2min)
            a2max = max(vis[i][1], a2max)

    # print a1min, a1max, a2min, a2max
    amax = a2min-1
    amin = max(1, -a1min+1)
    # print amax, amin
    if amax < amin:
        return 0
    else:
        if a is not None:
            return min(1, amax-amin+1)
        else:
            return amax-amin+1


class Reader(object):
    def __init__(self, filename=None):
        self.file = open(filename) if filename is not None else None
        self.case = 1

    def __readline(self):
        return self.file.next().strip() if self.file else raw_input()

    def next_case(self):
        self.file.next()
        self.case += 1

    def read_int(self): return int(self.__readline())
    def read_float(self): return float(self.__readline())
    def read_long(self): return long(self.__readline())
    def read_decimal(self): return decimal.Decimal(self.__readline())
    def read_str(self): return self.__readline()

    def read_int_list(self): return map(int, self.__readline().split())
    def read_float_list(self): return map(float, self.__readline().split())
    def read_long_list(self): return map(long, self.__readline().split())
    def read_decimal_list(self): return map(decimal.Decimal, self.__readline().split())
    def read_str_list(self): return self.__readline().split()

if __name__ == '__main__':
    filename = sys.argv[1] if len(sys.argv) > 1 else None
    f = Reader(filename)
    if f.file:
        while True:
            print "Case #%d\n"%f.case, solve(f)
            try:
                f.next_case()
            except StopIteration:
                break
    else:
        print solve(f)

Submission status: Accepted

Solution code:
import sys


def check(k, flag=False):
    fixed = [-1] * n
    q = [(0, k, False, None)]
    has_non_bipartite_loop = False
    while q:
        v, m, is_odd, a = q.pop()
        # print(v, m, is_odd, q, fixed)
        if fixed[v] != -1:
            p, was_odd = fixed[v]
            if is_odd == was_odd:
                if m != p:
                    return 0
                continue
            else:
                if m == p:
                    has_non_bipartite_loop = True
                    continue
                if flag:
                    return 0
                d = m - p if is_odd else p - m
                if d < 0:
                    return 0
                if d % 2:
                    return 0
                return check(k + d // 2, True)
        else:
            fixed[v] = (m, is_odd)

        for u, s in links[v]:
            if s - m < 1:
                if not is_odd:
                    return 0
                return check(k + m - s + 1, False)
            if u == a:
                continue
            q.append((u, s - m, not is_odd, v))

    if has_non_bipartite_loop:
        return 1

    min_is_odd = float('inf')
    for m, is_odd in fixed:
        if is_odd:
            min_is_odd = min(min_is_odd, m)
    return min_is_odd


n, m = map(int, input().split())
links = [set() for _ in range(n)]
for line in sys.stdin.readlines():
    u, v, s = map(int, line.split())
    u -= 1
    v -= 1
    links[u].add((v, s))
    links[v].add((u, s))
print(check(1))

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


def main():
    n,m = LI()
    a = [LI() for _ in range(m)]
    e = collections.defaultdict(list)
    for u,v,s in a:
        e[u].append((v,s))
        e[v].append((u,s))

    f = collections.defaultdict(bool)
    t = [None] * (n+1)
    t[e[1][0][0]] = -1000000
    nf = set()
    q = [e[1][0][0]]
    r = None
    while q:
        i = q.pop()
        for v,s in e[i]:
            if f[v]:
                continue
            if t[v] is None:
                t[v] = s - t[i]
                q.append(v)
            elif t[v] != s - t[i]:
                if v in nf:
                    return 0
                tv = (t[v] + s - t[i]) // 2
                t = [None] * (n+1)
                t[v] = tv
                nf.add(v)
                q = [v]
                break
        if nf:
            f = collections.defaultdict(bool)
        else:
            f[i] = True
    t[0] = inf
    t2 = t[:]
    tmi = t.index(min(t))
    f = collections.defaultdict(bool)
    t = [None] * (n+1)
    t[tmi] = 1
    nf = set()
    q = [tmi]
    r = None
    while q:
        i = q.pop()
        for v,s in e[i]:
            if f[v]:
                continue
            if t[v] is None:
                t[v] = s - t[i]
                q.append(v)
            elif t[v] != s - t[i]:
                if v in nf:
                    return 0
                tv = (t[v] + s - t[i]) // 2
                t = [None] * (n+1)
                t[v] = tv
                nf.add(v)
                q = [v]
                break
        if nf:
            f = collections.defaultdict(bool)
        else:
            f[i] = True
    r = inf
    if t[1:] == t2[1:]:
        if min(t[1:]) > 0:
            return 1
        return 0
    for i in range(1,n+1):
        if t[i] < 0:
            return 0
        if t[i] > t2[i]:
            continue
        if r > t[i]:
            r = t[i]


    return r



print(main())

Submission status: Accepted

Solution code:
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import defaultdict
from bisect import bisect

setrecursionlimit(10**6)

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

n, m = reads()

d = dict()
edges = [[] for _ in range(n)]

for i in range(m):
  u, v, s = reads()
  u, v = u-1, v-1
  edges[u].append((s, v))
  edges[v].append((s, u))

def quit(x):
  print(x)
  exit()

cond = [[None] * n for _ in range(2)]
cond[0][0] = 0

INF = 10**16

visited = [False] * n

def walk(x):
  if visited[x]:
    return
  visited[x] = True
  for s, y in edges[x]:
    for sig in range(2):
      if cond[sig][x] is not None:
        p = cond[sig][x]
        if cond[1-sig][y] is None or cond[1-sig][y] == s - p:
          cond[1-sig][y] = s - p
        else:
          quit(0)
    walk(y)

walk(0)

for i in range(n):
  if cond[0][i] is not None and cond[1][i] is not None:
    x = (cond[1][i] - cond[0][i]) // 2
    for i in range(n):
      if cond[0][i] is not None and cond[0][i] + x <= 0:
        quit(0)
      if cond[1][i] is not None and cond[1][i] - x <= 0:
        quit(0)
      if cond[0][i] is not None and cond[1][i] is not None and x + cond[0][i] != cond[1][i] - x:
        quit(0)
    quit(1)

pmin = min(p for p in cond[0] if p is not None)
nmin = min(p for p in cond[1] if p is not None)

print(max(0, nmin + pmin - 1))

Submission status: Runtime Error

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

n, m = map(int, input().split())
G = [[] for _ in range(n+1)]
for _ in range(m):
    u, v, s = map(int, input().split())
    G[u].append((v, s))
    G[v].append((u, s))
val = [None] * (n+1)
val[1] = (1, 0)
queue = deque([1])
while queue:
    u = queue.popleft()
    for v, s in G[u]:
        if val[v]:
            continue
        val[v] = (-val[u][0], s - val[u][1])
        queue.append(v)
ma = float('inf')
mi = 1
x = -1
for u in range(1, n+1):
    if val[u][0] == -1:
        ma = min(ma, val[u][1] - 1)
    else:
        mi = max(mi, -val[u][1] + 1)
    for v, s in G[u]:
        if u > v:
            continue
        if val[u][0] + val[v][0] == 0:
            if val[u][1] + val[v][1] != s:
                print(0)
                exit()
        else:
            a = val[u][0] + val[v][0]
            b = s - (val[u][1] + val[v][1])
            if a < 0:
                b *= -1
            if b <= 0 or b % 2 == 1:
                print(0)
                exit()
            if x == -1:
                x = b // 2
            elif x != b // 2:
                print(0)
                exit()
assert x == -1
print(max(ma - mi + 1, 0) if x == -1 else 1)

Submission status: Runtime Error

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

n, m = map(int, input().split())
G = [[] for _ in range(n+1)]
for _ in range(m):
    u, v, s = map(int, input().split())
    G[u].append((v, s))
    G[v].append((u, s))
val = [None] * (n+1)
val[1] = (1, 0)
queue = deque([1])
while queue:
    u = queue.popleft()
    for v, s in G[u]:
        if val[v]:
            continue
        val[v] = (-val[u][0], s - val[u][1])
        queue.append(v)
ma = float('inf')
mi = 1
x = -1
for u in range(1, n+1):
    if val[u][0] == -1:
        ma = min(ma, val[u][1] - 1)
    else:
        mi = max(mi, -val[u][1] + 1)
    for v, s in G[u]:
        if u > v:
            continue
        if val[u][0] + val[v][0] == 0:
            if val[u][1] + val[v][1] != s:
                print(0)
                exit()
        else:
            a = val[u][0] + val[v][0]
            b = s - (val[u][1] + val[v][1])
            if a < 0:
                b *= -1
            if b <= 0 or b % 2 == 1:
                print(0)
                exit()
            if x == -1:
                x = b // 2
            elif x != b // 2:
                print(0)
                exit()
assert False
print(max(ma - mi + 1, 0) if x == -1 else 1)

Submission status: Runtime Error

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

n, m = map(int, input().split())
G = [[] for _ in range(n+1)]
for _ in range(m):
    u, v, s = map(int, input().split())
    G[u].append((v, s))
    G[v].append((u, s))
queue = deque([1])
color = [-1] * (n+1)
color[1] = 0
ok = True
while queue:
    u = queue.popleft()
    for v, s in G[u]:
        if color[v] == -1:
            color[v] = 1 - color[u]
            queue.append(v)
        elif color[u] == color[v]:
            ok = False
            break
    assert ok
val = [None] * (n+1)
val[1] = (1, 0)
queue = deque([1])
while queue:
    u = queue.popleft()
    for v, s in G[u]:
        if val[v] is None:
            val[v] = (-val[u][0], s - val[u][1])
            queue.append(v)
ma = float('inf')
mi = 1
x = -1
for u in range(1, n+1):
    if val[u][0] == -1:
        ma = min(ma, val[u][1] - 1)
    else:
        mi = max(mi, -val[u][1] + 1)
    for v, s in G[u]:
        if u > v:
            continue
        if val[u][0] + val[v][0] == 0:
            if val[u][1] + val[v][1] != s:
                print(0)
                exit()
        else:
            a = val[u][0] + val[v][0]
            b = s - (val[u][1] + val[v][1])
            if a < 0:
                b *= -1
            if b <= 0 or b % 2 == 1:
                print(0)
                exit()
            if x == -1:
                x = b // 2
            elif x != b // 2:
                print(0)
                exit()
if x != -1:
    print(1)
else:
    print(max(ma - mi + 1, 0))

Submission status: Runtime Error

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007

n, m = LI()
G = [[] for _ in range(n)]
for i in range(m):
    u, v, s = LI()
    G[u - 1] += [(v - 1, s)]
    G[v - 1] += [(u - 1, s)]

num = [0] * n
def check(x, r):
    num[x] = r
    qq = [x]
    while qq:
        uii = qq.pop()
        for vii, sii in G[uii]:
            if (num[vii] and sii- num[uii] != num[vii]) or sii - r <= 0:
                return 0
            num[vii] = sii - r
            if num[vii] == 0:
                qq += [vii]
    return 1

flg = [0] * n
M = [0] * n
q = [(0, -1)]
depth = [-1] * n
depth[0] = 0
while q:
    ui, pre = q.pop()
    for vi, s in G[ui]:
        if vi == pre:
            continue
        depth[vi] = depth[ui] + 1
        flg[vi] = flg[ui] ^ 1
        M[vi] = s - M[ui]
        if vi == 0:
            if ((flg[vi] and M[vi] % 2) or M[vi] == 0) or (flg[vi] == 0 and M[vi]):
                print(0)
                exit()
            print(check(vi, M[vi] // 2))
            exit()
        q += [(vi, ui)]


L = [i for i in range(n)]
L.sort(key=lambda x:depth[x], reverse=True)
max_min = [[] for _ in range(n)]
for ii in L:
    max_i = INF
    min_i = 1
    for j, s in G[ii]:
        if j == depth[ii] - 1:
            continue
        max_r, min_r = max_min[j]
        max_i = min(max_i, s - min_r)
        min_i = max(min_i, s - max_r)
    if max_i <= min_i:
        print(0)
        exit()
    max_min[ii] = [max_i, min_i]


print(max_min[0][0] - max_min[0][1] + 1)

Submission status: Runtime Error

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007

n, m = LI()
G = [[] for _ in range(n)]
for i in range(m):
    u, v, s = LI()
    G[u - 1] += [(v - 1, s)]
    G[v - 1] += [(u - 1, s)]

num = [0] * n
def check(x, r):
    num[x] = r
    qq = [x]
    while qq:
        uii = qq.pop()
        for vii, sii in G[uii]:
            if (num[vii] and sii- num[uii] != num[vii]) or sii - r <= 0:
                return 0
            num[vii] = sii - r
            if num[vii] == 0:
                qq += [vii]
    return 1

flg = [0] * n
M = [0] * n
q = [(0, -1)]
depth = [-1] * n
depth[0] = 0
while q:
    ui, pre = q.pop()
    for vi, s in G[ui]:
        if vi == pre:
            continue
        depth[vi] = depth[ui] + 1
        flg[vi] = flg[ui] ^ 1
        M[vi] = s - M[ui]
        if vi == 0:
            if ((flg[vi] and M[vi] % 2) or M[vi] == 0) or (flg[vi] == 0 and M[vi]):
                print(0)
                exit()
            print(check(vi, M[vi] // 2))
            exit()
        q += [(vi, ui)]
        break


L = [i for i in range(n)]
L.sort(key=lambda x:depth[x], reverse=True)
max_min = [[] for _ in range(n)]
for ii in L:
    max_i = INF
    min_i = 1
    for j, s in G[ii]:
        if j == depth[ii] - 1:
            continue
        max_r, min_r = max_min[j]
        max_i = min(max_i, s - min_r)
        min_i = max(min_i, s - max_r)
    if max_i <= min_i:
        print(0)
        exit()
    max_min[ii] = [max_i, min_i]


print(max_min[0][0] - max_min[0][1] + 1)

Submission status: Runtime Error

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007

n, m = LI()
G = [[] for _ in range(n)]
for i in range(m):
    u, v, s = LI()
    G[u - 1] += [(v - 1, s)]
    G[v - 1] += [(u - 1, s)]

num = [0] * n
def check(x, r):
    num[x] = r
    qq = [x]
    while qq:
        uii = qq.pop()
        for vii, sii in G[uii]:
            if (num[vii] and sii- num[uii] != num[vii]) or sii - r <= 0:
                return 0
            num[vii] = sii - r
            if num[vii] == 0:
                qq += [vii]
    return 1

flg = [0] * n
M = [0] * n
q = [(0, -1)]
depth = [-1] * n
depth[0] = 0
while q:
    ui, pre = q.pop()
    for vi, s in G[ui]:
        if vi == pre:
            continue
        depth[vi] = depth[ui] + 1
        flg[vi] = flg[ui] ^ 1
        M[vi] = s - M[ui]
        if vi == 0:
            if (flg[vi] and M[vi] % 2) or (flg[vi] == 0 and M[vi]):
                print(0)
                exit()
            print(check(vi, M[vi] // 2))
            exit()
        q += [(vi, ui)]
        break


L = [i for i in range(n)]
L.sort(key=lambda x:depth[x], reverse=True)
max_min = [[] for _ in range(n)]
for ii in L:
    max_i = INF
    min_i = 1
    for j, s in G[ii]:
        if j == depth[ii] - 1:
            continue
        max_r, min_r = max_min[j]
        max_i = min(max_i, s - min_r)
        min_i = max(min_i, s - max_r)
    if max_i <= min_i:
        print(0)
        exit()
    max_min[ii] = [max_i, min_i]


print(max_min[0][0] - max_min[0][1] + 1)

Submission status: Runtime Error

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007

n, m = LI()
G = [[] for _ in range(n)]
for i in range(m):
    u, v, s = LI()
    G[u - 1] += [(v - 1, s)]
    G[v - 1] += [(u - 1, s)]

num = [0] * n
def check(x, r):
    num[x] = r
    qq = [x]
    while qq:
        uii = qq.pop()
        for vii, sii in G[uii]:
            if (num[vii] and sii- num[uii] != num[vii]) or sii - r <= 0:
                return 0
            num[vii] = sii - r
            if num[vii] == 0:
                qq += [vii]
    return 1

flg = [0] * n
M = [0] * n
q = [(0, -1)]
while q:
    ui, pre = q.pop()
    for vi, s in G[ui]:
        if vi == pre:
            continue
        flg[vi] = flg[ui] ^ 1
        M[vi] = s - M[ui]
        if vi == 0:
            if (flg[vi] and M[vi] % 2) or (flg[vi] == 0 and M[vi]):
                print(0)
                exit()
            print(check(vi, M[vi] // 2))
            exit()
        q += [(vi, ui)]
        break

ans = 1
def f(x, pre_x):
    max_i = INF
    min_i = 1
    for vv, ss in G[x]:
        if pre_x == vv:
            continue
        c_min, c_max = f(vv, x)
        max_i = min(max_i, ss - c_min)
        min_i = max(min_i, ss - c_max)
    if min_i > max_i:
        print(0)
        exit()
    return min_i, max_i

a, b = f(0, -1)
print(b - a + 1)

Submission status: Runtime Error

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007

n, m = LI()
G = [[] for _ in range(n)]
for i in range(m):
    u, v, s = LI()
    G[u - 1] += [[v - 1, s]]
    G[v - 1] += [[u - 1, s]]

num = [0] * n
def check(x, r):
    num[x] = r
    qq = [x]
    while qq:
        uii = qq.pop()
        for vii, sii in G[uii]:
            if (num[vii] and sii- num[uii] != num[vii]) or sii - r <= 0:
                return 0
            num[vii] = sii - r
            if num[vii] == 0:
                qq += [vii]
    return 1

flg = [0] * n
M = [0] * n
q = [(0, -1)]
while q:
    ui, pre = q.pop()
    for vi, s in G[ui]:
        if vi == pre:
            continue
        flg[vi] = flg[ui] ^ 1
        M[vi] = s - M[ui]
        if vi == 0:
            if (flg[vi] and M[vi] % 2) or (flg[vi] == 0 and M[vi]):
                print(0)
                exit()
            print(check(vi, M[vi] // 2))
            exit()
        q += [(vi, ui)]
        break

ans = 1
def f(x, pre_x):
    max_i = INF
    min_i = 1
    for vv, ss in G[x]:
        if pre_x == vv:
            continue
        c_min, c_max = f(vv, x)
        max_i = min(max_i, ss - c_min)
        min_i = max(min_i, ss - c_max)
    if min_i > max_i:
        print(0)
        exit()
    return min_i, max_i

a, b = f(0, -1)
print(b - a + 1)