Overview

In a tree-structured network, starting from initial infections (nodes with positive vulnerability values), infection spreads in a chain reaction under the condition “number of infected children > number of uninfected children.” The problem asks to simulate this process and determine the final number of infected nodes.

Analysis

Key Observations

1. Infection propagates only in the child → parent direction. Since it spreads bottom-up, whether a node becomes infected depends solely on the infection state of its child nodes.

2. Rephrasing the condition: Let \(c\) be the total number of children of node \(v\). If \(a\) is the number of infected children and \(b\) is the number of uninfected children, then \(a + b = c\). The condition \(a > b\) is equivalent to \(a > c - a\), i.e., \(2a > c\). In this form, we only need to track the number of infected children to make the determination.

3. Once a node is infected, it never becomes uninfected, so the number of infected children monotonically increases. This means once a node satisfies the condition, it will definitely become infected, and there is no need to check it twice.

Problem with the Naive Approach

Checking all nodes every round would result in worst-case \(O(N)\) rounds × \(O(N)\) nodes = \(O(N^2)\), risking TLE.

Solution

By using an “event-driven BFS” that only checks the parents of newly infected nodes as candidates, each node becomes infected at most once, making the approach efficient.

Algorithm

1. Initialization: Compute the number of children num_children[v] for each node, and infected_children[v] (the number of already-infected children) based on initially infected nodes.

2. Initial infection: Mark nodes with \(D_i > 0\) as infected and increment their parent’s infected_children.

3. Initial queue construction: Add to the queue all uninfected nodes that have children and satisfy the condition \(2 \times \text{infected\_children}[v] > \text{num\_children}[v]\).

4. Round-by-round BFS:

   • Infect all nodes in the current queue (reproducing simultaneous updates).
   • For each newly infected node’s parent, update infected_children and add to the next round’s queue if the condition is satisfied.
   • Repeat until the queue is empty.

5. Counting: Output the total number of infected nodes at the end.

Concrete Example

If the tree structure is 0 → 1 → {2, 3, 4}, with nodes 2 and 3 initially infected (\(D > 0\)) and node 4 uninfected: - Node 1 has 3 children, of which 2 are infected → \(2 \times 2 = 4 > 3\) → Node 1 also becomes infected.

Complexity

• Time complexity: \(O(N)\) (each node becomes infected at most once and enters the queue at most once)
• Space complexity: \(O(N)\) (for the tree’s adjacency list and various arrays)

Implementation Notes

• Reproducing simultaneous updates: By separating the queue into rounds (queue and next_queue), we ensure that nodes infected in the same round do not affect their parent within the same round.

• Simplifying the condition: Converting \(a > b\) to \(2a > c\) reduces the value managed at each node to just one: “the number of infected children.”

• Computer 0 is not subject to infection: When a node whose parent is computer 0 becomes infected, infected_children[0] is updated, but no infection check is performed on computer 0 itself (ensured by the check 1 <= p <= N).

• Preventing duplicate additions: Since the same node might be added to the queue multiple times, we check infected[v] during processing to prevent double infection.

  Source Code

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()

This editorial was generated by claude4.6opus-thinking.