C. Alyona and the Tree

http://codeforces.com/contest/682/problem/C

dfs，没什么好说的，直接看代码吧

 1 import java.util.ArrayList;
 2 import java.util.Scanner;
 3 
 4 
 5 public class Main {
 6     static long[] a = new long[(int) (1e5 + 50)];
 7     static ArrayList<Edge>[] al = new ArrayList[(int) (1e5 + 50)];
 8 
 9     public static void main(String[] args) {
10         Scanner io = new Scanner(System.in);
11         int n = io.nextInt();
12         for (int i = 1; i <= n; i++) a[i] = io.nextInt();
13         for (int i = 0; i < al.length; i++) al[i] = new ArrayList<>();
14         for (int x = 2, y, len; x <= n; x++) {
15             y = io.nextInt();
16             len = io.nextInt();
17             al[y].add(new Edge(x, len));
18         }
19         dfs(1, Long.MIN_VALUE/2);
20         System.out.println(ans);
21     }
22 
23 
24     static int ans = 0;
25 
26     static void dfs(int x, long max) {
27         if (max > a[x]) {
28             ans += child(x);
29             return;
30         }
31 
32         for (Edge e : al[x]) dfs(e.y, Math.max(e.len, max + e.len));
33     }
34 
35     static int child(int x) {
36         int size = 1;
37         for (Edge e : al[x]) size += child(e.y);
38         return size;
39     }
40 
41     static class Edge {
42         int y, len;
43 
44         public Edge(int y, int len) {
45             this.y = y;
46             this.len = len;
47         }
48     }
49 }