結果
問題 |
No.2618 除霊
|
ユーザー |
|
提出日時 | 2025-08-08 01:39:09 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,158 ms / 2,000 ms |
コード長 | 1,744 bytes |
コンパイル時間 | 313 ms |
コンパイル使用メモリ | 82,652 KB |
実行使用メモリ | 223,008 KB |
最終ジャッジ日時 | 2025-08-08 01:39:46 |
合計ジャッジ時間 | 35,786 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 43 |
ソースコード
## 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 eff_flags = set() if (i + 1) in v_set: for w in next_nodes[i]: ghost_magic_num[w] -= 1 eff_flags.add(w) 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 ans -= next_effectives[w][i] else: if ghost_magic_num[w] == 0 and w in eff_flags: 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()