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: Wrong Answer

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] 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: Wrong Answer

Solution code:
print(1)

Submission status: Wrong Answer

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] 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: Wrong Answer

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:
                a *= -1
                b *= -1
            q, r = divmod(b, a)
            if b <= 0 or r != 0:
                print(0)
                exit()
            if x == -1:
                x = q
            elif x != q:
                print(0)
                exit()
if x != -1:
    print(1)
else:
    print(max(ma - mi + 1, 0))

Submission status: Wrong Answer

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 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:
                a *= -1
                b *= -1
            q, r = divmod(b, a)
            if b <= 0 or r != 0:
                print(0)
                exit()
            if x == -1:
                x = q
            elif x != q:
                print(0)
                exit()
if x != -1:
    print(1)
else:
    print(max(ma - mi + 1, 0))

Submission status: Wrong Answer

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 = -float('inf')
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 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 b % a != 0:
                print(0)
                exit()
            c = b // a
            if c <= 0:
                print(0)
                exit()
            if x == -1:
                x = c
            elif x != c:
                print(0)
                exit()
if x != -1:
    print(1)
else:
    print(max(ma - mi + 1, 0))

Submission status: Wrong Answer

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 = -float('inf')
x = -1
print(val)
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 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 b % a != 0:
                print(0)
                exit()
            c = b // a
            if c <= 0:
                print(0)
                exit()
            if x == -1:
                x = c
            elif x != c:
                print(0)
                exit()
if x != -1:
    print(1)
else:
    print(max(ma - mi + 1, 0))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)

N, M = map(int, input().split())
edge = [[] for _ in range(N)]

smax = 10**18
L = [1] * N
U = [10 ** 18] * N
for i in range(M):
    u, v, s = map(int, input().split())
    u -= 1
    v -= 1
    edge[u].append((v, s, i))
    edge[v].append((u, s, ~i))
    U[u] = min(s-1, U[u])
    U[v] = min(s-1, U[v])
    if s < smax:
        smax = s
        root = u

# 1点を決めると他の点も一意に決まる
used_e1 = [0] * M
used_e2 = [0] * M
seen = [0] * N

node = [root]
seen[root] = 1
order = []
while node:
    a = node.pop()
    order.append(a)
    la = L[a]
    ua = U[a]
    for b, s, i in edge[a]:
        if i >= 0:
            if used_e2[i] == 1:
                continue
            used_e1[i] = 1
        else:
            i = ~i
            if used_e1[i] == 1:
                continue
            used_e2[i] = 1
        L[b] = max(L[b], s - ua)
        U[b] = min(U[b], s - la)
        if L[b] > U[b]:
            print(0)
            exit()
        if seen[b] != 1:
            node.append(b)
            seen[b] = 1

seen[order[-1]] = 2
for a in order[::-1]:
    la = L[a]
    ua = U[a]
    for b, s, i in edge[a]:
        if i >= 0 and used_e1[i] == 0:
            L[b] = max(L[b], s - ua)
            U[b] = min(U[b], s - la)
        elif i < 0 and used_e2[~i] == 0:
            L[b] = max(L[b], s - ua)
            U[b] = min(U[b], s - la)
        if L[b] > U[b]:
            print(0)
            exit()

print(U[root] - L[root] + 1)

Submission status: Wrong Answer

Solution code:
from collections import *
N,M=map(int,input().split())
X=[-1]*N
X[0]=1
G=[[] for i in range(N)]
u,v,s=0,0,0
for i in range(M):
  u,v,s=map(int,input().split())
  u,v=u-1,v-1
  G[u].append((v,s))
  G[v].append((u,s))
Q=deque()
S=set()
def qao(x):
  if x in S:
    return False
  S.add(x)
  Q.append(x)
  return True

D=[0]*N
def bfs(x):
  v=0
  for i in range(len(Q)):
    v=Q.popleft()
    for j in range(len(G[v])):
      if qao(G[v][j][0]):
        D[G[v][j][0]]=x
        X[G[v][j][0]]=G[v][j][1]-X[v]
  return len(Q)

qao(0)
for i in range(N):
  if bfs(i+1)==0:
    break
if min(X)<1:
  print(0)
  exit()
for i in range(N):
  for j in range(len(G[i])):
    if X[i]+X[G[i][j][0]]!=G[i][j][1]:
      print(0)
      exit()
P=10**18
if N<=M:
  P=1
for i in range(N):
  if D[i]&1:
    P=min(P,X[i])
print(P)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**9)
n,m=map(int,input().split())

graph=[[] for _ in range(n+1)]
for _ in range(m):
  u,v,s=map(int,input().split())
  graph[u].append((v,s))
  graph[v].append((u,s))
  
def has_cycle(u,par):
  visited[u]=True
  
  ret=False
  for v,w in graph[u]:
    if v==par:
      continue     
    if visited[v]:
      return True
    else:
      if has_cycle(v,u):
        ret=True
      
  return ret

visited=[False]*(n+1)
cyclic=has_cycle(1,0)

min_even=float("inf")
min_odd=float("inf")
def add_score_acyclic(u,par,weight,depth):
  visited[u]=True
  point_list[u]=weight-point_list[par]
  if depth%2==0:
    global min_even
    min_even=min(min_even,point_list[u])
  else:
    global min_odd
    min_odd=min(min_odd,point_list[u])
  
  for v,w in graph[u]:
    if v==par:
      continue     
    add_score_acyclic(v,u,w,depth+1)

if cyclic:
  #temp
  print(1)
else:
  point_list=[0]*(n+1)
  add_score_acyclic(1,0,0,0)
  
  #print(point_list)
  #print(min_even,min_odd)
  print(max(0,min_even+min_odd-1))

Submission status: Wrong Answer

Solution code:
from collections import deque
N, M = map(int, input().split())
A = [[] for _ in range(N)]

for i in range(M):
  u,v,s = map(int, input().split())
  u,v = u-1, v-1
  A[u].append((v,s))
  A[v].append((u,s))

# up[i] A[0]=tとしたときの A[i] = a + t > 0 <=> t > up[i]
# dw[i] A[0]=tとしたときの A[i] = a - t > 0 <=> t < dw[i]
UP = [ -1 for _ in range(N)]
DW = [ 10**9+1 for _ in range(N)]
UP[0] = 0
#DW[0] = 0

# nodeじゃなくて、edgeを全探索する必要がある気がする。。。
# bfsすれば良いのか？
def solve():
  visited = [ False for _ in range(N)]
  willSearch = [ False for _ in range(N)]
  Q = deque()
  # (node, depth)
  Q.append((0,0))
  while Q:
    now, depth = Q.pop()
    visited[now] = True
    for nxt, cost in A[now]:
      if depth % 2 == 1:
        UP[nxt] = max(UP[nxt], DW[now] - cost)
      else:
        DW[nxt] = min(DW[nxt], UP[now] + cost)
      # 訪問済みなら、エッジはPUSHしなくて良い
      if visited[nxt] or willSearch[nxt]:
        continue
      Q.append((nxt,depth+1))
  
solve()
#print(UP)
#print(DW)
up, dw = 0, 10**9
for x in UP:
  if x >= 0:
    up = max(up,x)
for x in DW:
  if x <= 10**9:
    dw = min(dw,x)
    
print(dw-up-1)
    
               
"""
1 -(5)-> 2 -(3)-> 3 - (8)-> 4
1がtだと、2は5-t、　３はt-2, 4は10-t

"""

Submission status: Wrong Answer

Solution code:
import sys,bisect,string,math,time,functools,random,fractions
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
def Golf():n,*t=map(int,open(0).read().split())
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1) # sample usage
    mp=[boundary]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def bit_combination(n,base=2):
    rt=[]
    for tb in range(base**n):s=[tb//(base**bt)%base for bt in range(n)];rt+=[s]
    return rt
def gcd(x,y):
    if y==0:return x
    if x%y==0:return y
    while x%y!=0:x,y=y,x%y
    return y
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)
 
YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
FourNb=[(-1,0),(1,0),(0,1),(0,-1)];EightNb=[(-1,0),(1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('WENS',FourNb));cursol=dict(zip('LRUD',FourNb))
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
read=sys.stdin.buffer.read
readline=sys.stdin.buffer.readline
input=lambda: sys.stdin.readline().rstrip()

class Tree:
    def __init__(self,inp_size=None,ls=None,init=True,index=0):
        self.LCA_init_stat=False
        self.ETtable=[]
        if init:
            if ls==None:
                self.stdin(inp_size,index=index)
            else:
                self.size=len(ls)+1
                self.edges,_=GI(self.size,self.size-1,ls,index=index)
        return
 
    def stdin(self,inp_size=None,index=1):
        if inp_size==None:
            self.size=int(input())
        else:
            self.size=inp_size
        self.edges,_=GI(self.size,self.size-1,index=index)
        return
    
    def listin(self,ls,index=0):
        self.size=len(ls)+1
        self.edges,_=GI(self.size,self.size-1,ls,index=index)
        return
 
    def __str__(self):
        return  str(self.edges)
 
    def dfs(self,x,func=lambda prv,nx,dist:prv+dist,root_v=0):
        q=deque()
        q.append(x)
        v=[-1]*self.size
        v[x]=root_v
        while q:
            c=q.pop()
            for nb,d in self.edges[c]:
                if v[nb]==-1:
                    q.append(nb)
                    v[nb]=func(v[c],nb,d)
        return v
 
    def EulerTour(self,x):
        q=deque()
        q.append(x)
        self.depth=[None]*self.size
        self.depth[x]=0
        self.ETtable=[]
        self.ETdepth=[]
        self.ETin=[-1]*self.size
        self.ETout=[-1]*self.size
        cnt=0
        while q:
            c=q.pop()
            if c<0:
                ce=~c
            else:
                ce=c
                for nb,d in self.edges[ce]:
                    if self.depth[nb]==None:
                        q.append(~ce)
                        q.append(nb)
                        self.depth[nb]=self.depth[ce]+1
            self.ETtable.append(ce)
            self.ETdepth.append(self.depth[ce])
            if self.ETin[ce]==-1:
                self.ETin[ce]=cnt
            else:
                self.ETout[ce]=cnt
            cnt+=1
        return
    
    def LCA_init(self,root):
        self.EulerTour(root)
        self.st=SparseTable(self.ETdepth,init_func=min,init_idl=inf)
        self.LCA_init_stat=True
        return
    
    def LCA(self,root,x,y):
        if self.LCA_init_stat==False:
            self.LCA_init(root)
        xin,xout=self.ETin[x],self.ETout[x]
        yin,yout=self.ETin[y],self.ETout[y]
        a=min(xin,yin)
        b=max(xout,yout,xin,yin)
        id_of_min_dep_in_et=self.st.query_id(a,b+1)
        return self.ETtable[id_of_min_dep_in_et]
 
class SparseTable: # O(N log N) for init, O(1) for query(l,r)
    def __init__(self,ls,init_func=min,init_idl=float('inf')):
        self.func=init_func
        self.idl=init_idl
        self.size=len(ls)
        self.N0=self.size.bit_length()
        self.table=[ls[:]]
        self.index=[list(range(self.size))]
        self.lg=[0]*(self.size+1)
        
        for i in range(2,self.size+1):
            self.lg[i]=self.lg[i>>1]+1
 
        for i in range(self.N0):
            tmp=[self.func(self.table[i][j],self.table[i][min(j+(1<<i),self.size-1)]) for j in range(self.size)]
            tmp_id=[self.index[i][j] if self.table[i][j]==self.func(self.table[i][j],self.table[i][min(j+(1<<i),self.size-1)]) else self.index[i][min(j+(1<<i),self.size-1)] for j in range(self.size)]
            self.table+=[tmp]
            self.index+=[tmp_id]
    
    # return func of [l,r)
    def query(self,l,r):
        if r>self.size:r=self.size
        #N=(r-l).bit_length()-1
        N=self.lg[r-l]
        return self.func(self.table[N][l],self.table[N][max(0,r-(1<<N))])
    
    # return index of which val[i] = func of v among [l,r)
    def query_id(self,l,r):
        if r>self.size:r=self.size
        #N=(r-l).bit_length()-1
        N=self.lg[r-l]
        a,b=self.index[N][l],self.index[N][max(0,r-(1<<N))]
        if self.table[0][a]==self.func(self.table[N][l],self.table[N][max(0,r-(1<<N))]):
            b=a
        return b
    
    def __str__(self):
        return str(self.table[0])
 
    def print(self):
        for i in self.table:
            print(*i)

def dijkstra(edge,st):
    # edge=[[(v_to,dist_to_v),...],[],...]
    # initialize: def: d=dist(st,i), prev=[previous vertex in minimum path], q[]
    n=len(edge)
    d=[(0 if st==i else inf) for i in range(n)]
    prev=[0]*n
    q=[(j,i) for i,j in enumerate(d)]
    heapify(q)
    v=[False]*n
    # calc
    while q:
        dist,cur=heappop(q)
        if v[cur]:
            continue
        v[cur]=True
        for dst,dist in edge[cur]:
            alt=d[cur]+dist
            if alt<d[dst]:
                d[dst]=alt
                prev[dst]=cur
                heappush(q,(alt,dst))
    return d,prev

show_flg=False
show_flg=True
ans=0



n,m=LI()
g,ip=GI(n,m)

def check(x,k):
    func=lambda x,y,z:z-x
    q=deque()
    q.append(x)
    v=[-1]*n
    v[x]=k
    while q:
        c=q.pop()
        for nb,d in g[c]:
            if v[nb]==-1:
                q.append(nb)
                v[nb]=func(v[c],nb,d)
                if v[nb]<=0:
                    0#return False
    for a,b,s in ip:
        a-=1
        b-=1
        if v[a]+v[b]!=s:
            0#return False
#    show((x,k),v)
    return v

v0=check(0,0)
print(v0)
v1=check(0,1)
print(v1)

print([j-i for i,j in zip(v0,v1)])

show(g)

Submission status: Wrong Answer

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

def bfs():
    q = deque([0])
    dist = [-1]*n
    dist[0] = 0
    a = [-1]*n
    a[0] = 0
    
    while q:
        v = q.popleft()
        
        for nv, w in G[v]:
            if dist[nv]==-1:
                dist[nv] = dist[v]+1
                a[nv] = w-a[v]
                q.append(nv)
    
    return dist, a
                
n, m = map(int, input().split())
G = [[] for _ in range(n)]
edges = []

for _ in range(m):
    u, v, s = map(int, input().split())
    G[u-1].append((v-1, s))
    G[v-1].append((u-1, s))
    edges.append((u-1, v-1, s))

dist, a = bfs()
ts = set()

for u, v, s in edges:
    if dist[u]%2!=dist[v]%2:
        if a[u]+a[v]!=s:
            print(0)
            exit()
    else:
        if dist[u]%2==0:
            if s-a[u]-a[v]>=2 and (s-a[u]-a[v])%2==0:
                ts.add((s-a[u]-a[v])//2)
            else:
                print(0)
                exit()
        else:
            if a[u]+a[v]-s>=2 and (a[u]+a[v]-s)%2==0:
                ts.add((a[u]+a[v]-s)//2)
            else:
                print(0)
                exit()

if len(ts)>=2:
    print(0)
elif len(ts)==1:
    print(1)
else:
    l = 1
    r = 10**18
    
    for i in range(n):
        if dist[i]%2==0:
            l = max(l, -a[i]+1)
        else:
            r = min(r, a[i]-1)
    
    print(max(0, r-l+1))

Submission status: Wrong Answer

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

def bfs():
    q = deque([0])
    dist = [-1]*n
    dist[0] = 0
    a = [-1]*n
    a[0] = 0
    
    while q:
        v = q.popleft()
        
        for nv, w in G[v]:
            if dist[nv]==-1:
                dist[nv] = dist[v]+1
                a[nv] = w-a[v]
                q.append(nv)
    
    return dist, a
                
n, m = map(int, input().split())
G = [[] for _ in range(n)]
edges = []

for _ in range(m):
    u, v, s = map(int, input().split())
    G[u-1].append((v-1, s))
    G[v-1].append((u-1, s))
    edges.append((u-1, v-1, s))

dist, a = bfs()
ts = []

for u, v, s in edges:
    if dist[u]%2!=dist[v]%2:
        if a[u]+a[v]!=s:
            print(0)
            exit()
    else:
        if dist[u]%2==0:
            if s-a[u]-a[v]>=2 and (s-a[u]-a[v])%2==0:
                ts.append((s-a[u]-a[v])//2)
            else:
                print(0)
                exit()
        else:
            if a[u]+a[v]-s>=2 and (a[u]+a[v]-s)%2==0:
                ts.append((a[u]+a[v]-s)//2)
            else:
                print(0)
                exit()

if len(ts)>=2:
    print(0)
elif len(ts)==1:
    print(1)
else:
    l = 1
    r = 10**18
    
    for i in range(n):
        if dist[i]%2==0:
            l = max(l, -a[i]+1)
        else:
            r = min(r, a[i]-1)
    
    print(max(0, r-l+1))

Submission status: Wrong Answer

Solution code:
def main():
    ### 初期設定 ###
    n, m = map(int, input().split())
    uvs = [list(map(int, input().split())) for _ in [0]*m]
    g = [[] for _ in [0]*n]
    [g[a-1].append([b-1, c]) for a, b, c in uvs]
    [g[b-1].append([a-1, c]) for a, b, c in uvs]

    ### 閉路検出 ###
    # やるべきこと
    # DFSで閉路を見つける
    # ・奇閉路が見つかったとき
    # ⇒答えは高々一つなので探索打ち切り。
    # ⇒閉路=[a1,a2,a3,a4,a5]
    # ⇒閉路の辺=[s1,s2,s3,s4,s5]のとき、
    # ⇒a1=((s1+s3+s5)-(s2+s4))//2 に固定される。
    # ・偶閉路が見つかったとき
    # ⇒閉路=[a1,a2,a3,a4,a5,a6]
    # ⇒閉路の辺=[s1,s2,s3,s4,s5,s6]のとき、
    # ⇒S=s1+s3+s5-s2-s4-s6を計算する。
    # ⇒S=0ならば探索を続行する。
    # ⇒S!=0ならば0を出力して強制終了。

    g2 = [{(j, k) for j, k in gg} for gg in g]  # グラフのset化
    q = [0]  # 探索用キュー
    q_dict = {0: 0}  # 頂点がqの中の何番目か
    ac_even = [0]  # 累積和（偶数）
    ac_odd = [0]  # 累積和（奇数）
    flag = False  # 奇閉路があるかどうか
    while q:
        i = q[-1]
        # 行先があった場合
        if g2[i]:
            j, k = g2[i].pop()
            g2[j].remove((i, k))
            # 閉路検出時
            if j in q_dict:
                l = q_dict[j]
                loop_size = len(q)-l
                if len(q) % 2 == 1:
                    ac_even.append(ac_even[-1]+k)
                else:
                    ac_odd.append(ac_odd[-1]+k)
                # 偶閉路があったとき
                if loop_size % 2 == 0:
                    print("偶閉路だよ")
                    # ダメな感じの閉路なら終了、それ以外は続行
                    if ac_even[-1]-ac_even[-loop_size//2-1] != ac_odd[-1]-ac_odd[-loop_size//2-1]:
                        print(0)
                        return
                    if len(q) % 2 == 1:
                        ac_even.pop()
                    else:
                        ac_odd.pop()
                # 奇閉路があったとき
                else:
                    flag = True
                    if len(q) % 2 == 1:
                        s = ac_even[-1]-ac_even[-loop_size//2-1] - \
                            ac_odd[-1]+ac_odd[-loop_size//2]
                    else:
                        s = ac_odd[-1]-ac_odd[-loop_size//2-1] - \
                            ac_even[-1]+ac_even[-loop_size//2]
                    if s <= 0 or s % 2 != 0:
                        print(0)
                        return
                    else:
                        ini = [j, s//2]
                        break
            # それ以外
            else:
                q_dict[j] = len(q)
                q.append(j)
                if len(q) % 2 == 0:
                    ac_even.append(ac_even[-1]+k)
                else:
                    ac_odd.append(ac_odd[-1]+k)
        # なかったとき
        else:
            if len(q) % 2 == 0:
                ac_even.pop()
            else:
                ac_odd.pop()
            q.pop()
            q_dict.pop(i)

    ### 探索終了後（奇閉路ありの場合） ###
    # ⇒先程決めた頂点からDFSをスタート。
    # ⇒矛盾が生じたら終了、生じなかったら1を出力。
    g2 = [{(j, k) for j, k in gg} for gg in g]  # グラフのset化
    if flag:
        i, j = ini
        visited = [-1]*n
        visited[i] = j
        q = [i]
        while q:
            i = q[-1]
            j = visited[i]
            if g2[i]:
                k, l = g2[i].pop()
                q.append(k)
                g2[k].remove((i, l))
                new = l-j
                if new <= 0:
                    print(0)
                    return
                if visited[k] == -1:
                    visited[k] = new
                elif visited[k] != new:
                    print(0)
                    return
            else:
                q.pop()
        print(1)
    ### 探索終了後（奇閉路なしの場合） ###
    # ⇒どこかの頂点からDFSをスタート。
    # ⇒各頂点の取りうる値の範囲を1～10**9からスタートさせ、
    # ⇒徐々に狭めていく。
    # ⇒戻る際に過去に通った点にも随時更新をかけていく。
    else:
        visited = [None]*n
        visited[0] = [1, 10**9]
        q = [0]
        s = []
        while q:
            i = q[-1]
            m, M = visited[i]
            if g2[i]:
                j, k = g2[i].pop()
                q.append(j)
                s.append(k)
                g2[j].remove((i, k))
                newM = max(k-m, 0)
                newm = max(k-M, 1)
                if newM == 0:
                    print(0)
                    return
                if visited[j] != None:
                    newM = min(newM, visited[j][1])
                    newm = max(newm, visited[j][0])
                    if newm > newM:
                        print(0)
                        return
                visited[j] = [newm, newM]
            else:
                q.pop()
                if q:
                    j = q[-1]
                    k = s.pop()
                    m, M = visited[i]
                    newM = max(k-m, 0)
                    newm = max(k-M, 1)
                    if newM == 0:
                        print(0)
                        return
                    if visited[j] != None:
                        newM = min(newM, visited[j][1])
                        newm = max(newm, visited[j][0])
                        if newm > newM:
                            print(0)
                            return
                    visited[j] = [newm, newM]
        print(visited[0][1]-visited[0][0]+1)


main()