image.png

    1. import java.util.*;
    3. public class Test{
    4.     static int n;
    5.     static final int maxn = 6005;
    7.     static int cnt = 0;
    9.     //edges[i][0] 相当于 edges[i].to
    10.     //edges[i][1] 相当于 edges[i].next
    11.     static int[][] edges = new int[maxn][2];
    12.     static int[] head = new int[maxn];
    13.     static boolean[] is_head = new boolean[maxn];
    14.     static boolean[] visited = new boolean[maxn];
    16.     static int[][] dp = new int[maxn][2];
    18.     static void dfs(int k){
    19.         visited[k] = true;
    20.         for(int i = head[k]; i != -1; i = edges[i][1]){
    21.             if(visited[edges[i][0]]){
    22.                 continue;
    23.             }
    24.             dfs(edges[i][0]);
    25.             dp[k][1] += dp[edges[i][0]][0];
    26.             dp[k][0] += Math.max(dp[edges[i][0]][0], dp[edges[i][0]][1]);
    27.         }
    28.     }
    29.     static void add_edge(int u, int v){
    30.         cnt++;
    31.         edges[cnt][0] = v;
    32.         edges[cnt][1] = head[u];
    33.         head[u] = cnt;
    34.     }
    36.     public static void main(String[] args) {
    37.         Scanner sc = new Scanner(System.in);
    38.         n = sc.nextInt();
    39.         for(int i = 1; i <= n; i++){
    40.             dp[i][1] = sc.nextInt();
    41.         }
    43.         //初始化head[]
    44.         Arrays.fill(head, -1);
    46.         int k, l;
    47.         for(int i = 0; i < n - 1; i++){
    48.             l = sc.nextInt();
    49.             k = sc.nextInt();
    50.             add_edge(k, l);
    51.             is_head[l] = true;
    52.         }
    54.         for (int i = 1; i <= n; i++){
    55.             if(!is_head[i]){
    56.                 dfs(i);
    57.                 System.out.println(Math.max(dp[i][0], dp[i][1]));
    58.                 return;
    59.             }
    60.         }
    61.     }
    62. }