fork download
copy 
  1. import java.util.*;
  2.  
  3. public class Main {
  4. static long[] sum;   // sum[i] = best downward path sum starting from node i (node i is included)
  5. static int[] b;      // b[i] = value at node i
  6.  
  7.  
  8. public static void DFS(int node, List<Integer>[] G, int[] used, int[] parent) {
  9.     used[node] = 1; // mark node as visited
  10.  
  11.     // Explore all children first
  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.  
  20.     long bestChild = 0; // 0 means we can ignore negative children
  21.     for (int child : G[node]) {
  22.         if (child == parent[node]) continue; // skip parent
  23.         bestChild = Math.max(bestChild, sum[child]);
  24.     }
  25.  
  26.     // Include this node's value + best child path
  27.     sum[node] = b[node] + bestChild;
  28. }
  29.  
  30. public static void main(String[] args) {
  31.     Scanner scanner = new Scanner(System.in);
  32.     int n = scanner.nextInt();
  33.  
  34.     sum = new long[n + 1];
  35.     b = new int[n + 1];
  36.     List<Integer>[] G = new List[n + 1];
  37.     for (int i = 0; i <= n; i++) G[i] = new ArrayList<>();
  38.  
  39.  
  40.     for (int i = 1; i <= n; i++) {
  41.         b[i] = scanner.nextInt();
  42.     }
  43.  
  44.  
  45.     for (int i = 1; i <= n - 1; i++) {
  46.         int u = scanner.nextInt();
  47.         int v = scanner.nextInt();
  48.         G[u].add(v);
  49.         G[v].add(u);
  50.     }
  51.     int[] used = new int[n + 1];
  52.     int[] parent = new int[n + 1];
  53.     DFS(1, G, used, parent);
  54.     long answer = Long.MIN_VALUE ;
  55.     for (int i = 1; i <= n; i++) {
  56.         answer = Math.max(answer, sum[i]);
  57.     }
  58. 	 System.out.println(answer);
  59. }
  60. }
  61.  
Success #stdin #stdout 0.18s 56576KB
comments (?)
stdin
copy 
5
1 -2 3 4 -1
1 2
1 3
3 4
3 5
stdout
copy 
8
https://ideone.com/jQOWPx
language:
Java (HotSpot 12)
created:
3 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!