fork download
copy 
  1.  
  2. import java.util.*;
  3.  
  4. public class Main {
  5.  
  6.     static long[] sum;
  7.     static int[] b;
  8.  
  9.     public static void DFS(int node, ArrayList<Integer>[] G, int[] used, int[] parent) {
  10.         used[node] = 1;
  11.  
  12.         for (int u : G[node]) {
  13.             if (used[u] == 0) {
  14.                 parent[u] = node;
  15.                 DFS(u, G, used, parent);
  16.             }
  17.         }
  18.  
  19.         long s = 0;
  20.         for (int child : G[node]) {
  21.             if (child == parent[node]) continue;
  22.             s += sum[child];
  23.         }
  24.  
  25.         sum[node] = b[node] + s;
  26.     }
  27.  
  28.     public static void main(String[] args) {
  29.         Scanner scanner = new Scanner(System.in);
  30.  
  31.         int n = scanner.nextInt();
  32.         sum = new long[n + 1];
  33.         b = new int[n + 1];
  34.  
  35.         for (int i = 1; i <= n; i++) {
  36.             b[i] = scanner.nextInt();
  37.         }
  38.  
  39.         ArrayList<Integer>[] G = new ArrayList[n + 1];
  40.         for (int i = 0; i <= n; i++) {
  41.             G[i] = new ArrayList<>();
  42.         }
  43.  
  44.         for (int i = 1; i <= n - 1; i++) {
  45.             int u = scanner.nextInt();
  46.             int v = scanner.nextInt();
  47.             G[u].add(v);
  48.             G[v].add(u);
  49.         }
  50.  
  51.         int[] used = new int[n + 1];
  52.         int[] parent = new int[n + 1];
  53.  
  54.         DFS(1, G, used, parent);
  55.  
  56.         long answer = Long.MIN_VALUE;
  57.         for (int i = 1; i <= n; i++) {
  58.             answer = Math.max(answer, sum[i]);
  59.         }
  60.  
  61.         System.out.println(answer);
  62.     }
  63. }
  64.  
  65.  
Success #stdin #stdout 0.15s 54580KB
comments (?)
stdin
copy 
5
3 2 1 4 5
1 2
1 3
3 4
3 5
stdout
copy 
15
https://ideone.com/SySOyd
language:
Java (HotSpot 12)
created:
4 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!