java代码

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.Arrays;
import java.util.Scanner;

public class Main {

    static int n;
    static long a[];
    static long[] f;
    static Edge[] edges;
    static int head[];
    static int ans = 0;
    static boolean vis[];

    static void dfs(int u) {

        vis[u] = true;
        for (int i = head[u]; i != 0; i = edges[i].next) {
            int j = edges[i].to;
            if (!vis[j]) {
                dfs(j);
                f[u] += Math.max(f[j], 0);
            }
        }
        vis[u] = false;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        a = new long[n + 1];
        f = new long[n + 1];
        vis = new boolean[n + 1];
        Arrays.fill(vis, false);
        edges = new Edge[2*(n+1)+1];
        head = new int[n + 1];
        int cnt = 1;
        for (int i = 1; i <= n; i++) {
            a[i] = scanner.nextInt();
             f[i] = a[i];
        }

        for (int i = 0; i < n - 1; i++) {
            int a, b;
            a = scanner.nextInt();
            b = scanner.nextInt();
            edges[cnt] = new Edge(a, b, head[a]);
            head[a] = cnt;
            cnt++;
            edges[cnt] = new Edge(b, a, head[b]);
            head[b] = cnt;
            cnt++;
        }
        long res = f[1];
        dfs(1);
        for (int i = 1; i <= n; i++) {
            res = Math.max(res, f[i]);
        }
        System.out.println(res);
    }

}


class Edge {
    int from, to, next;

    public Edge(int from, int to, int next) {
        this.from = from;
        this.to = to;
        this.next = next;
    }

}

终于还是验证了

 static void dfs(int u, int fa) {
     f[u] = a[u];
     for (int i = head[u]; i != 0; i = edges[i].next) {
     int j = edges[i].to;
     if (j != fa) {
     dfs(j, u);
     f[u] += Math.max(f[j], 0);
     }
     }
     }

    static void dfs(int u) {

        vis[u] = true;
        for (int i = head[u]; i != 0; i = edges[i].next) {
            int j = edges[i].to;
            if (!vis[j]) {
                dfs(j);
                // Systemzhe.out.println(f[j]);
                f[u] += Math.max(f[j], 0);
            }
        }
        vis[u] = false;
    }

这两个就是一个意思