結果
問題 |
No.2618 除霊
|
ユーザー |
|
提出日時 | 2025-08-08 01:27:23 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,723 bytes |
コンパイル時間 | 383 ms |
コンパイル使用メモリ | 82,316 KB |
実行使用メモリ | 222,928 KB |
最終ジャッジ日時 | 2025-08-08 01:28:07 |
合計ジャッジ時間 | 36,065 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 4 WA * 39 |
ソースコード
## https://yukicoder.me/problems/no/2618 def main(): N = int(input()) next_nodes = [[] for _ in range(N)] for _ in range(N - 1): a, b = map(int, input().split()) next_nodes[a - 1].append(b - 1) next_nodes[b - 1].append(a - 1) M = int(input()) V = list(map(int, input().split())) ghost_magic_num = [0] * N for v in V: ghost_magic_num[v - 1] += 1 for w in next_nodes[v - 1]: ghost_magic_num[w] += 1 next_effectives = [{} for _ in range(N)] for v in V: ans = 0 for w in next_nodes[v - 1]: if ghost_magic_num[w] == 1: ans += 1 for w in next_nodes[v - 1]: if ghost_magic_num[w] == 1: next_effectives[v - 1][w] = ans - 1 else: next_effectives[v - 1][w] = ans base_answer = 0 for i in range(N): if ghost_magic_num[i] > 0: base_answer += 1 v_set = set(V) for i in range(N): ans = base_answer if (i + 1) in v_set: for w in next_nodes[i]: ghost_magic_num[w] -= 1 if ghost_magic_num[i] > 0: ans -= 1 for w in next_nodes[i]: if (w + 1) in v_set: if ghost_magic_num[w] == 1: ans -= 1 if i in next_effectives[w]: ans -= next_effectives[w][i] else: if ghost_magic_num[w] == 0: ans -= 1 print(ans) if (i + 1) in v_set: for w in next_nodes[i]: ghost_magic_num[w] += 1 if __name__ == "__main__": main()