package Acwing算法练习.第五章dp;

import java.util.Arrays;
import java.util.Scanner;
//f[u][0]表示以u为根节点，并且不包括u的最大快乐指数
//f[u][1]表示以u为根节点，并且包括u的最大快乐指数
public class 没有上司的舞会 {
    static int N = 100010;
    static int[] happy = new int[N];
    static boolean[] has_fa = new boolean[N];
    static int[][] f = new int[N][2];
    static int[] e = new int[N],ne = new int[N],h = new int[N];
    static int idx;
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for(int i=1;i<=n;i++) happy[i] = sc.nextInt();
        Arrays.fill(h,-1);
        for(int i=0;i<n-1;i++)//n-1条边
        {
            int b = sc.nextInt();
            int a = sc.nextInt();
            has_fa[b] = true;//如果有父节点，就true
            add(a,b);
        }

        int root = 1;
        while(has_fa[root]) root++;
        dfs(root);
        System.out.println(Math.max(f[root][0],f[root][1]));

    }

    static void dfs(int u)
    {
        f[u][1] = happy[u];
        for(int i=h[u];i!=-1;i=ne[i])
        {
            int j = e[i];
            dfs(j);//子结点
            f[u][1] += f[j][0];
            f[u][0] += Math.max(f[j][1],f[j][0]);
        }
    }

    static void add(int a,int b)
    {
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx++;
    }

}