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: Runtime Error

Solution code:
import numpy as np

def find(position):
    a = np.where(position == edge[0])[0]
    b = np.where(position == edge[1])[0]
    c = np.int32(np.append(a,b))
    d = np.int32(np.append(np.ones(len(a)), np.zeros(len(b))))
    
    return c,d

def find_henkou_edge(henkousareta):
    inds = np.array([]).astype(np.int32)
    for a in henkousareta:
        ind,dotti = find(a)
        inds = np.append(inds,ind)
    inds = np.unique(inds)
    
    return inds

def check(inds):
    ok = True
    for ind in inds:
        i = edge[:,ind]
#         print(i)
#         print(num[i])
        if (num[i] != -9999).all():
#             print(num[i].any())
            if not sum(num[i]) == ss[ind]:
                ok = False
    return ok

def check_henkou(henkousareta):
    inds = find_henkou_edge(henkousareta)
#     print(inds)
    ok = check(inds)
    return ok

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

uu = []
vv = []
ss = []
for k in range(m):
    u,v,s = map(int,input().split())
    uu.append(u)
    vv.append(v)
    ss.append(s)
uu = np.array(uu) -1
vv = np.array(vv) -1
ss = np.array(ss)

edge = np.vstack([uu,vv])

mi = np.min(ss)
armi = np.argmin(ss)
num = np.int32(np.zeros(n)) - 9999
cand = range(1,mi)

ruikei = 0
for c in cand:
    num = np.int32(np.zeros(n)) - 9999
#     print(c)
    num[armi] = c
    ind_tar = armi
    
    while True:
        ind,dotti = find(ind_tar)
        henkousareta = []
        ok_for = True
        for k in range(len(ind)):
            temp = dotti[k],ind[k]
            temp = edge[temp]
            if num[temp] == -9999:
                num[temp] = ss[ind[k]] - num[ind_tar]
                if num[temp] < 1:
                    ok_for = False
                    break
            else:
                if not num[temp] == ss[ind[k]] - num[ind_tar]:
                    ok_for = False
                    break
            henkousareta.append(temp)
#         print(num)
#         print(ok_for)
        if ok_for == False:
            ok = False
            break
        ok = check_henkou(henkousareta)
#         print(henkousareta)
        if ok == False:
            break
        if not np.min(num) == -9999:
            break
        ind,dotti = find(np.where(num == -9999)[0][0])
        ind_tar = edge[dotti[0],ind[0]]
#         print(num)
    ruikei += ok
print(ruikei)

Submission status: Runtime Error

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[1] = -1000
    nf = set()
    q = [1]
    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:]:
        return 1
    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]

    f = collections.defaultdict(bool)
    t = [None] * (n+1)
    t[2] = -1000
    nf = set()
    q = [2]
    r2 = 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
    r2 = inf
    if t[1:] == t2[1:]:
        return 1
    for i in range(1,n+1):
        if t[i] < 0:
            return 0
        if t[i] <= t2[i]:
            continue
        if r2 > t[i]:
            r2 = t[i]

    return min(r,r2)



print(main())