結果

問題 No.3514 Majority Driven Tree
コンテスト
ユーザー tomerun
提出日時 2026-04-24 23:05:06
言語 Crystal
(1.19.1)
コンパイル:
crystal build -Donline_judge -o a.out --release --no-debug _filename_
実行:
./a.out
結果
WA  
実行時間 -
コード長 1,148 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 13,077 ms
コンパイル使用メモリ 342,636 KB
実行使用メモリ 7,976 KB
最終ジャッジ日時 2026-04-24 23:05:44
合計ジャッジ時間 15,326 ms
ジャッジサーバーID
（参考情報） 		judge4_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 2 WA * 35
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

n = read_line.to_i
g = Array.new(n) { [] of Int32 }
(n - 1).times do
  a, b = read_line.split.map(&.to_i)
  g[a - 1] << b - 1
  g[b - 1] << a - 1
end
q = [0]
parent = Array.new(n, -1)
n.times do |i|
  cur = q[i]
  g[cur].each do |adj|
    next if parent[cur] == adj
    parent[adj] = cur
    q << adj
  end
end
dp0 = Array.new(n, n)
dp1 = Array.new(n, n)
(n - 1).downto(0) do |i|
  cur = q[i]
  par = parent[cur]
  if g[cur].size == 1 && i != 0
    dp0[cur] = 1
    dp1[cur] = 0
    next
  end
  cvs = [] of Tuple(Int32, Int32)
  sum_1 = 1
  g[cur].each do |adj|
    next if par == adj
    sum_1 += dp1[adj]
    cvs << {dp0[adj], dp1[adj]}
  end
  cvs.sort_by! { |v0, v1| v0 - v1 }
  hc = g[cur].size // 2 + 1
  if hc <= cvs.size
    dp0[cur] = 0
    dp1[cur] = 0
    hc.times do |j|
      dp0[cur] += cvs[j][0]
    end
    hc.upto(cvs.size - 1) do |j|
      dp0[cur] += cvs[j][1]
    end
  end
  if hc - 1 <= cvs.size
    (hc - 1).times do |j|
      dp1[cur] += cvs[j][0]
    end
    (hc - 1).upto(cvs.size - 1) do |j|
      dp1[cur] += cvs[j][1]
    end
  end
  dp0[cur] = {dp0[cur], sum_1}.min
  dp1[cur] = {dp1[cur], sum_1}.min
end
puts dp0[0]
0