Overview

In a network forming a tree structure, following the rule that infection propagates only from children to parents, we need to determine the total number of computers that ultimately become infected.

Analysis

Understanding the Key Property

The most important point of this problem is that “infection propagates only from children to parents, not from parents to children.” Because of this, whether a computer \(v\) becomes infected is uniquely determined by whether it satisfies one of the following two conditions: 1. \(v\) itself is initially infected (\(D_v > 0\)) 2. Among \(v\)’s child computers, the number of those that ultimately became infected \(a\) is greater than the number of those that did not become infected \(b\) (\(a > b\))

The infection state of a parent or siblings does not affect the infection state of \(v\). Therefore, we can determine infection states in a bottom-up manner, from the “leaves” (endpoints of the tree) toward the “root (central server).”

Efficient Approach

A naive simulation that scans all nodes at every step according to the rules would result in \(O(N^2)\) time complexity in the worst case (e.g., a path graph), causing a Time Limit Exceeded (TLE) verdict. However, by processing nodes in order of “parent nodes whose children’s infection states have all been determined,” we can construct an \(O(N)\) algorithm that processes each node exactly once. This is the same idea as topological sort or the typical approach of reducing degrees from the leaves of a tree (leaf removal).

Algorithm

1. Initialization:

   • Compute the “original number of children” total_children[i] and the “number of unprocessed children” child_count[i] for each node \(i\).
   • Set the infection state of nodes with \(D_i > 0\) to \(1\) (infected), and all others to \(0\) (uninfected).
   • Add all nodes with child_count[i] == 0 (leaf nodes) to a Queue.

2. Bottom-up Propagation:

   • Dequeue a node \(u\) from the queue.
   • Let \(p\) be the parent of \(u\).
   • If \(u\) is infected (\(S[u] == 1\)), increment the “number of infected children” infected_child_count[p] of parent \(p\) by \(1\).
   • Decrement the “number of unprocessed children” child_count[p] of parent \(p\) by \(1\).
   • If child_count[p] becomes \(0\), then the infection states of all children of parent \(p\) have been determined. At this point, we perform the infection judgment for \(p\):
     • If \(D_p > 0\) or infected_child_count[p] * 2 > total_children[p], set node \(p\) to infected state (\(1\)).
     • Otherwise, set it to uninfected state (\(0\)).
     • Add the judged parent \(p\) to the queue (only if \(p \ge 1\); exclude the central server \(0\)).

3. Counting:

   • Count and output the total number of computers (from \(1\) to \(N\)) whose final infection state is \(1\).

Complexity

• Time Complexity: \(O(N)\)
  • Each node enters the queue at most once, and the transition to its parent occurs exactly once per node. Therefore, the entire process completes in \(O(N)\) time.
• Space Complexity: \(O(N)\)
  • The arrays managing parent, number of children, infection states, etc., all have size \(N + 1\), so memory usage is \(O(N)\).

Implementation Notes

• Majority Judgment:

  • The condition \(a > b\) can be transformed as follows: if the total number of child nodes is \(T\), then \(a > T - a \iff 2a > T\).
  • In the implementation, using infected_child_count[p] * 2 > total_children[p] avoids floating-point division and allows accurate judgment using only integers.

• Excluding the Central Server (Computer 0):

  • Since computer 0 does not get infected, care must be taken not to add it to the queue or include it in the final answer count.

    Source Code

import sys


def solve():
    # Read all inputs from standard input
    input_data = sys.stdin.read().split()
    if not input_data:
        return

    N = int(input_data[0])

    # 1-indexed arrays
    P = [0] * (N + 1)
    D = [0] * (N + 1)
    child_count = [0] * (N + 1)
    total_children = [0] * (N + 1)
    S = [0] * (N + 1)

    idx = 1
    for i in range(1, N + 1):
        p = int(input_data[idx])
        d = int(input_data[idx + 1])
        idx += 2
        P[i] = p
        D[i] = d
        child_count[p] += 1
        total_children[p] += 1
        if d > 0:
            S[i] = 1

    # Queue for leaf nodes (excluding 0)
    Q = [i for i in range(1, N + 1) if child_count[i] == 0]

    infected_child_count = [0] * (N + 1)

    head = 0
    while head < len(Q):
        u = Q[head]
        head += 1

        p = P[u]
        if S[u] == 1:
            infected_child_count[p] += 1

        child_count[p] -= 1
        if child_count[p] == 0 and p >= 1:
            if D[p] > 0 or infected_child_count[p] * 2 > total_children[p]:
                S[p] = 1
            else:
                S[p] = 0
            Q.append(p)

    # Output the total number of infected computers (excluding computer 0)
    print(sum(S[1:]))


if __name__ == "__main__":
    solve()

This editorial was generated by gemini-3.5-flash-thinking.