結果

問題 No.3425 Mod K Graph Increments (Easy)
コンテスト
ユーザー mentos_grape
提出日時 2026-01-11 14:10:22
言語 Python3
(3.14.2 + numpy 2.4.0 + scipy 1.16.3)
結果
AC  
実行時間 443 ms / 2,000 ms
コード長 1,944 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 478 ms
コンパイル使用メモリ 20,700 KB
実行使用メモリ 49,212 KB
最終ジャッジ日時 2026-01-11 14:10:28
合計ジャッジ時間 4,028 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 7
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys


sys.setrecursionlimit(300000)

def main():
   
    input = sys.stdin.read
    data = input().split()
    iterator = iter(data)
    
    try:
        num_test_cases = int(next(iterator))
    except StopIteration:
        return

    results = []
    
    for _ in range(num_test_cases):
        try:
            N = int(next(iterator))
            M = int(next(iterator)) # M = N - 1
            K = int(next(iterator))
        except StopIteration:
            break
        
        
        adj = [[] for _ in range(N)]
        for _ in range(M):
            u = int(next(iterator)) - 1 
            v = int(next(iterator)) - 1
            adj[u].append(v)
            adj[v].append(u)
        
      
        B = []
        for _ in range(N):
            B.append(int(next(iterator)))
        
      
        order = []
        stack = [0]
        visited = [False] * N
        visited[0] = True
        parent = [-1] * N
        
       
        while stack:
            u = stack.pop()
            order.append(u)
            
            for v in adj[u]:
                if not visited[v]:
                    visited[v] = True
                    parent[v] = u
                    stack.append(v)
        
       
        current_val = [0] * N
        possible = True
        
        
        for i in range(N - 1, -1, -1):
            u = order[i]
            
        
            have = current_val[u] % K
            target = B[u]
            
         
            ops_needed = (target - have) % K
            
            p = parent[u]
            if p != -1:
             
                current_val[p] = (current_val[p] + ops_needed) % K
            else:
                if ops_needed != 0:
                    possible = False
        
        if possible:
            results.append("Yes")
        else:
            results.append("No")

    
    print('\n'.join(results))

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