C. Alyona and the Tree
发布时间:2020-12-16 09:18:04 所属栏目:百科 来源:网络整理
导读:? 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 ArrayListEd
? 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 } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |