题解分享
题解分享简介
生命之树(编程题) - 题解
看到还没有人提交，我交一下我的题解
```
import java.io.BufferedInputStream;
import java.io.BufferedOutputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Scanner;
public class Main {
static ArrayList<Integer> graph[];
static int n, v[];
static long dp[];
public static void main(String[] args) {
Scanner scanner = new Scanner(new BufferedInputStream(System.in));
PrintWriter writer = new PrintWriter(new BufferedOutputStream(System.out));
long res = 0;
n = scanner.nextInt();
graph = new ArrayList[n + 1];
v = new int[n + 1];
dp = new long[n + 1];
for (int i = 1; i <= n; i++) {
v[i] = scanner.nextInt();
graph[i] = new ArrayList<Integer>();
}
for (int i = 1; i < n; i++) {
int a = scanner.nextInt();
int b = scanner.nextInt();
graph[a].add(b);
graph[b].add(a);
}
dfs(1, -1);
res=dp[1];
for(int i=2;i<=n;i++) {
res=Math.max(res, dp[i]);
}
writer.print(res);
writer.flush();
scanner.close();
}
static void dfs(int current, int father) {
dp[current] = v[current];
for (int son : graph[current]) {
if(son!=father) {
dfs(son, current);
dp[current]+=Math.max(0l, dp[son]);
}
}
}
}
```
查看全文
0
0
0
2
