Overview

This problem requires simulating how a virus spreads through a tree-structured network rooted at the central server (computer \(0\)) according to given rules, and determining the final number of infected computers.

By leveraging the property that infection propagation is “one-directional, from children to parents only,” we can solve this with an \(O(N)\) algorithm that determines states bottom-up from the leaves toward the root.

---

Analysis

1. Organizing the Propagation Condition

Let’s organize the condition in Rule 2: “the number of infected children \(a\) is greater than the number of non-infected children \(b\) (\(a > b\)).” If we denote the total number of children of computer \(v\) as \(C_v\), then the number of non-infected children can be expressed as \(b = C_v - a\). Therefore, the propagation condition can be rewritten as follows:

\[a > C_v - a \iff 2a > C_v\]

To avoid division with decimals (\(a > C_v / 2\)), it is safe and free from precision issues to use the integer comparison \(2a > C_v\) in the program.

2. Direction of Propagation and Dependencies

The most important point of this problem is that “infection only occurs from children to parents, and never propagates back from parents to children.”

Whether a computer \(u\) ultimately becomes infected is determined by satisfying one of the following two conditions: 1. Its vulnerability value is positive in the initial state (\(D_u > 0\)) 2. When the final infection states of \(u\)’s child computers are determined, the number of infected children \(a_u\) satisfies \(2a_u > C_u\)

Since a parent’s infection state does not affect its children, there is a bottom-up dependency relationship: “once all children’s infection states are determined, the parent’s infection state is also uniquely determined.”

3. Why Doesn’t a Naive Simulation Work?

If we perform a naive simulation of “repeatedly scanning the entire network until no new computers become infected,” in the worst case (e.g., a tree connected in a single path \(1 \to 2 \to \dots \to N\)), infection progresses by only one computer per step, resulting in \(O(N^2)\) total time, which would exceed the time limit (TLE).

4. Batch Processing in Bottom-Up Order

Since the dependency is one-directional from “children \(\to\) parents,” if we determine infection states in the order from the leaves (vertices with no children) toward the root (central server \(0\)), the judgment for each computer needs to be performed exactly once.

Specifically, we process as follows: 1. Starting from the root (\(0\)), obtain a topological order (where parents come before children) using breadth-first search (BFS) or similar. 2. Traverse this order in reverse (from leaves toward parents, then toward the root). 3. For each computer \(u\), perform the infection judgment using the current “number of infected children \(a_u\),” and if it becomes infected, increment \(a_{P_u}\) for its parent \(P_u\) by \(1\).

This allows us to determine the correct final state in just a single traversal, without performing repeated simulations.

---

Algorithm

1. Building the Adjacency List and Counting Children: From each computer’s parent \(P_i\), create a children list for each vertex. Also, compute the total number of children \(C_u\) for each vertex \(u\).

2. Obtaining Topological Order: Perform BFS starting from computer \(0\), recording vertices in the array order in the order they are visited. This ensures that in order, “parents always appear before children.”

3. Bottom-Up Processing in Reverse Order: Process vertices \(u\) from the end of order (leaf side) in sequence.

   • If \(u = 0\) (the central server), skip it as it cannot be infected.
   • If \(D_u > 0\) or \(2 \times a_u > C_u\), computer \(u\) is judged as infected.
     • Increment the infection count by \(1\).
     • Increment the “number of infected children” \(a_{P_u}\) of \(u\)’s parent \(P_u\) by \(1\).

4. Output the Answer: Output the final infection count.

---

Complexity

• Time Complexity: \(O(N)\)

  • Building the tree, topological sorting via BFS, and the reverse traversal can all be performed in linear time with respect to the number of vertices and edges (both \(O(N)\)). Therefore, the overall complexity is \(O(N)\), which is sufficiently fast.

• Space Complexity: \(O(N)\)

  • The tree’s adjacency list, the array storing topological order, and the arrays managing the number of children and infection state for each vertex all use memory proportional to the number of vertices \(N\).

---

Implementation Notes

• Handling the Central Server (Computer \(0\)): Computer \(0\) does not get infected. In the bottom-up loop, skip processing when \(u = 0\). Also, be careful not to include it in the final answer count.

• Integer Comparison: By expressing the condition “a majority of children are infected” as 2 * a[u] > C[u], we can perform the judgment without using any floating-point arithmetic.

  Source Code

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    if (!(cin >> N)) return 0;

    vector<int> P(N + 1);
    vector<long long> D(N + 1);
    vector<vector<int>> children(N + 1);

    for (int i = 1; i <= N; ++i) {
        cin >> P[i] >> D[i];
        children[P[i]].push_back(i);
    }

    // BFS to get topological order (parent before children)
    vector<int> order;
    order.reserve(N + 1);
    queue<int> q;
    q.push(0);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        order.push_back(u);
        for (int v : children[u]) {
            q.push(v);
        }
    }

    vector<int> C(N + 1, 0);
    for (int i = 1; i <= N; ++i) {
        C[P[i]]++;
    }

    vector<int> a(N + 1, 0);
    vector<bool> infected(N + 1, false);
    int ans = 0;

    for (int i = (int)order.size() - 1; i >= 0; --i) {
        int u = order[i];
        if (u == 0) continue;

        if (D[u] > 0 || 2 * a[u] > C[u]) {
            infected[u] = true;
            ans++;
            a[P[u]]++;
        }
    }

    cout << ans << "\n";

    return 0;
}

---

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