概要

木構造のネットワークにおいて、初期感染（脆弱性値が正のノード）から始まり、「感染した子の数 > 感染していない子の数」という条件で連鎖的に感染が広がる過程をシミュレーションし、最終的な感染台数を求める問題です。

考察

重要な気づき

1. 感染は子→親方向のみに伝播します。つまりボトムアップに広がるため、あるノードが感染するかどうかは、その子ノードの感染状態のみで決まります。

2. 条件の言い換え: ノード \(v\) の子の総数を \(c\) とすると、感染した子の数を \(a\)、感染していない子の数を \(b\) としたとき \(a + b = c\) です。条件 \(a > b\) は \(a > c - a\)、すなわち \(2a > c\) と等価です。この形にすると、感染した子の数だけ追跡すれば判定できます。

3. 一度感染したノードは感染が解除されないため、感染した子の数は単調に増加します。つまり、一度条件を満たしたノードは必ず感染し、二度チェックする必要がありません。

素朴なアプローチの問題

毎ラウンド全ノードをチェックする方法では、最悪 \(O(N)\) ラウンド × \(O(N)\) ノード = \(O(N^2)\) となりTLEの恐れがあります。

解決策

新たに感染したノードの親だけを次の候補としてチェックする「イベント駆動型BFS」を使えば、各ノードは高々1回しか感染しないため効率的です。

アルゴリズム

1. 初期化: 各ノードの子の数 num_children[v] と、初期感染ノードに基づく infected_children[v]（感染済みの子の数）を計算する。

2. 初期感染: \(D_i > 0\) のノードを感染状態にし、その親の infected_children を加算する。

3. 初期キュー構築: 未感染かつ子を持つノードで、条件 \(2 \times \text{infected\_children}[v] > \text{num\_children}[v]\) を満たすものをキューに入れる。

4. ラウンドごとのBFS:

   • 現在のキュー内の全ノードを感染させる（同時更新を再現）。
   • 新たに感染したノードの親について infected_children を更新し、条件を満たせば次ラウンドのキューに追加。
   • キューが空になるまで繰り返す。

5. 集計: 最終的に感染したノードの総数を出力。

具体例

木構造が 0 → 1 → {2, 3, 4} で、ノード2,3が初期感染（\(D > 0\)）、ノード4が未感染の場合： - ノード1の子は3台、うち感染2台 → \(2 \times 2 = 4 > 3\) → ノード1も感染。

計算量

• 時間計算量: \(O(N)\)（各ノードは高々1回感染し、1回だけキューに入るため）
• 空間計算量: \(O(N)\)（木の隣接リスト、各種配列の保持）

実装のポイント

• 同時更新の再現: キューをラウンドごとに分ける（queue と next_queue）ことで、同じラウンドで感染したノードが同ラウンド内で親に影響を与えないようにする。

• 条件の簡略化: \(a > b\) を \(2a > c\) に変換することで、各ノードで管理する値を「感染済みの子の数」1つだけに削減。

• コンピュータ0は感染対象外: 親がコンピュータ0のノードが感染した場合、infected_children[0] は更新するが、コンピュータ0自体の感染判定は行わない（1 <= p <= N のチェック）。

• 重複追加の防止: キューに同じノードが複数回入る可能性があるため、処理時に infected[v] を確認して二重感染を防ぐ。

  ソースコード

import sys
from collections import deque

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    
    parent = [0] * (N + 1)
    D = [0] * (N + 1)
    children = [[] for _ in range(N + 1)]
    
    for i in range(1, N + 1):
        P = int(input_data[idx]); idx += 1
        d = int(input_data[idx]); idx += 1
        parent[i] = P
        D[i] = d
        children[P].append(i)
    
    # infected[i] for i=1..N
    infected = [False] * (N + 1)
    
    # Step 1: Initial infection
    for i in range(1, N + 1):
        if D[i] > 0:
            infected[i] = True
    
    # For each node v (1..N), we need to track:
    # - number of children that are infected (a)
    # - number of children that are not infected (b)
    # v gets infected by propagation if a > b, i.e., a > (total_children - a), i.e., 2*a > total_children
    
    # We'll use a bottom-up approach.
    # When a node becomes infected, it can potentially cause its parent to become infected.
    
    # For each node, count infected children
    num_children = [0] * (N + 1)
    infected_children = [0] * (N + 1)
    
    for v in range(0, N + 1):
        num_children[v] = len(children[v])
    
    for i in range(1, N + 1):
        if infected[i]:
            p = parent[i]
            infected_children[p] += 1
    
    # BFS/queue-based propagation
    # Initially, queue all non-infected nodes v (1..N) that satisfy condition
    # But it's more efficient to think about it from the perspective of:
    # When a node becomes infected, check if its parent now satisfies the condition.
    
    # Actually, the problem says each "round" checks all nodes simultaneously.
    # But we can simulate this more efficiently:
    # A node v becomes infected when infected_children[v] > num_children[v] - infected_children[v]
    # i.e., 2 * infected_children[v] > num_children[v]
    # Once infected, it increments infected_children of its parent.
    
    # However, the simultaneous update matters: in one round, multiple nodes can become infected,
    # and a node that becomes infected in round k should only affect its parent in round k+1.
    
    # We need to do BFS by rounds (level-by-level BFS).
    
    # First round: find all non-infected nodes that satisfy condition based on initial state
    queue = deque()
    
    for v in range(1, N + 1):
        if not infected[v] and num_children[v] > 0:
            if 2 * infected_children[v] > num_children[v]:
                queue.append(v)
    
    while queue:
        next_queue = deque()
        # Process all nodes in current round
        newly_infected = []
        while queue:
            v = queue.popleft()
            if infected[v]:
                continue
            # Re-check condition (might have been added multiple times)
            if 2 * infected_children[v] > num_children[v]:
                infected[v] = True
                newly_infected.append(v)
        
        # Update parents
        for v in newly_infected:
            p = parent[v]
            if p >= 0:
                infected_children[p] += 1
                # Check if parent (if 1..N and not infected) now satisfies condition
                if 1 <= p <= N and not infected[p] and num_children[p] > 0:
                    if 2 * infected_children[p] > num_children[p]:
                        next_queue.append(p)
        
        queue = next_queue
    
    count = sum(1 for i in range(1, N + 1) if infected[i])
    print(count)

main()

この解説は claude4.6opus-thinking によって生成されました。