ACcode
import java.util.*;
public class Main{
static int N=100010;
static int M=2*N;
static long f[]=new long[N];
static long w[]=new long[N];
static int e[]=new int[M];
static int ne[]=new int[M];
static int h[]=new int[N];
static int idx;
public static void add(int a,int b){
//邻接表存边
e[idx]=b;
ne[idx]=h[a];
h[a]=idx;
idx++;
}
public static void dfs(int u,int father){
f[u]=w[u];
//f[u]等于u的权值
for(int i=h[u];i!=-1;i=ne[i]){
//遍历他的所有邻节点
int j=e[i];
if(j==father)continue;
//防止往回搜索,造成结果错误
dfs(j,u);
//以j为根u为父亲再继续往下搜
f[u]+=Math.max(f[j],0);
//以u为根的j的子树的权值之和
}
}
public static void main(String []args ) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
Arrays.fill(h,-1);//初始化
for(int i=1;i<=n;i++)w[i]=sc.nextInt();//树节点的权值
for(int i=0;i<n-1;i++){
int a=sc.nextInt();
int b=sc.nextInt();
//由于是树,存在双向边a-->b,b-->a
add(a,b);
add(b,a);
}
//从根节点1开始,设置根节点的父亲为-1。
//避免往回搜
dfs(1,-1);
long res=f[1];
//先以res为f[1]的作最大值
for(int i=2;i<n;i++)res=Math.max(res,f[i]);
//更新以i为根的子树的连通块的最大值
System.out.println(res);
}
}
ACcode(快读快写)
import java.util.*;
import java.io.*;
public class Main{
static int N=100010;
static int M=2*N;
static long f[]=new long[N];
static long w[]=new long[N];
static int e[]=new int[M];
static int ne[]=new int[M];
static int h[]=new int[N];
static int idx;
public static void add(int a,int b){
e[idx]=b;
ne[idx]=h[a];
h[a]=idx;
idx++;
}
public static void dfs(int u,int father){
f[u]=w[u];
for(int i=h[u];i!=-1;i=ne[i]){
int j=e[i];
if(j==father)continue;
dfs(j,u);
f[u]+=Math.max(f[j],0);
}
}
public static void main(String []args )throws IOException {
BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
String s1[]=bf.readLine().split(" ");
int n=Integer.parseInt(s1[0]);
String str[]=bf.readLine().split(" ");
Arrays.fill(h,-1);
for(int i=1;i<=n;i++)w[i]=Integer.parseInt(str[i-1]);
for(int i=0;i<n-1;i++){
String s[]=bf.readLine().split(" ");
int a=Integer.parseInt(s[0]);
int b=Integer.parseInt(s[1]);
add(a,b);
add(b,a);
}
dfs(1,-1);
long res=f[1];
for(int i=2;i<n;i++)res=Math.max(res,f[i]);
System.out.println(res);
}
}