この問題は DFS の練習問題です。

ウイルスの感染は子から親への方向のみに起こります。したがって、どのコンピュータも、各子が最終的にウイルスに感染するかどうかが分かれば、自身が最終的にウイルスに感染するかどうかがわかります。

これは根からの DFS の帰りがけ順に判定することで処理することができます。

計算量は \(O(N)\) です。

擬似コード

kansen = [False, ...,] // 各コンピュータが感染するかどうかを表す配列
function dfs(v):
  // 最終的にvが感染するかどうか判定し、kansen[v] に格納する
  for vの子 vv:
    dfs(vv)
    if kansen[vv]:
      ng +=1
    else:
      ok += 1
  kansen[v] = ng > ok or D[v] > 0:

実装例 (C++)

#include<bits/stdc++.h>
using namespace std;

int main(){
  int n;
  cin >> n;
  vector<int> d(n+1);
  vector<vector<int>> child(n+1);
  for(int i=1; i<=n; i++){
    int p;
    cin >> p >> d[i];
    child[p].push_back(i);
  }
  
  vector<bool>kansen(n+1);
  
  auto dfs=[&](auto self, int v) -> void{
    int ok = 0, ng = 0;
    for(auto vv: child[v]){
      self(self, vv);
      if(kansen[vv]){
        ng++;
      }else{
        ok++;
      }
    }
    kansen[v] = (ng > ok) || (d[v] > 0);
  };
  
  dfs(dfs, 0);
  int ans = 0;
  for(int i=1; i<=n; i++){
    if(kansen[i]){
      ans++;
    }
  }
  cout << ans << endl;
}

実装例 (Python)

import sys
sys.setrecursionlimit(10**7)

N = int(input())
D = [-1] * (N+1)
child = [[] for _ in range(N+1)]
for i in range(1, N+1):
  p, d = map(int, input().split())
  child[p].append(i)
  D[i] = d

kansen = [False] * (N+1)

def dfs(v):
  ok, ng = 0, 0
  for vv in child[v]:
    dfs(vv)
    if kansen[vv]:
      ng += 1
    else:
      ok += 1
  kansen[v] = (ng > ok) or (D[v] > 0)

dfs(0)
print(sum(kansen[1:]))