結果

問題 No.3425 Mod K Graph Increments (Easy)
コンテスト
ユーザー KA37RI
提出日時 2026-01-11 15:42:53
言語 Rust
(1.92.0 + proconio + num)
結果
AC  
実行時間 55 ms / 2,000 ms
コード長 1,029 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 25,175 ms
コンパイル使用メモリ 414,380 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2026-01-11 15:43:21
合計ジャッジ時間 26,695 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 7
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

use proconio::{input, marker::Usize1};

fn solve() -> bool {
  input! {
    n: usize,
    m: usize,
    k: u64,
    uv: [(Usize1, Usize1); m],
    b: [u64; n],
  }
  assert_eq!(m, n - 1);
  let mut graph = vec![vec![]; n];
  for &(ui, vi) in uv.iter() {
    graph[ui].push(vi);
    graph[vi].push(ui);
  }
  let mut a = vec![0; n];
  let mut visited = vec![false; n];
  visited[0] = true;
  let mut parent = vec![0; n];
  let mut stack = vec![(0, true)];
  while let Some((cur, f)) = stack.pop() {
    if f {
      for &nxt in graph[cur].iter() {
        if visited[nxt] {
          continue;
        }
        visited[nxt] = true;
        parent[nxt] = cur;
        stack.push((nxt, false));
        stack.push((nxt, true));
      }
    } else {
      let d = (k + b[cur] - a[cur]) % k;
      a[cur] += d;
      a[cur] %= k;
      a[parent[cur]] += d;
      a[parent[cur]] %= k;
    }
  }
  a[0] == b[0]
}

fn main() {
  input! {
    t: usize,
  }
  for _ in 0..t {
    println!("{}", if solve() { "Yes" } else { "No" });
  }
}
0