package yukicoder; import java.util.ArrayList; import java.util.Scanner; public class Main{ public static void main(String[] args) { new Main().solve(); } ArrayList[] edges = new ArrayList[50000]; int[] A; // dp[v][A[u]]:頂点vの子頂点uをvにつないだ時の門松列の総数 int[][] dp = new int[1000][50000]; int[] num_up = new int[1000];// num_up[v]:頂点vの持つ数字より大きい数を持つ子頂点の数 int[] num_down = new int[1000];// num_up[v]:頂点vの持つ数字より小さい数を持つ子頂点の数 int[] sc_down = new int[1000];// sc_up[v]:頂点vの子頂点がvより小さくなるような場合に含める最大の門松列の総数 int[] sc_up = new int[1000];// sc_down[v]:頂点vの子頂点がvより大きくなるな場合に含める最大の門松列の総数 int dfs(int cur, int pre) { int ret = 0; for (int i = 0; i < edges[cur].size(); i++) { int u = edges[cur].get(i); if (pre != u) { ret = Math.max(ret, dfs(u, cur)); if (A[cur] > A[u]) { if (dp[u][A[cur]] >= 0) { dp[cur][A[u]] = Math.max(sc_up[u] - dp[u][A[cur]], dp[cur][A[u]]); } else { dp[cur][A[u]] = Math.max(num_up[u] + sc_up[u], dp[cur][A[u]]); } } else if (A[cur] < A[u]) { if (dp[u][A[cur]] >= 0) { dp[cur][A[cur]] = Math.max(sc_down[u] - dp[u][A[cur]], dp[cur][A[cur]]); } else { dp[cur][A[u]] = Math.max(num_down[u] + sc_down[u], dp[cur][A[u]]); } } } } for (int i = 0; i < 1000; i++) { if (dp[cur][i] >= 0) { if (A[cur] > i) { num_down[cur]++; sc_down[cur] += dp[cur][i]; } else if (A[cur] < i) { num_up[cur]++; sc_up[cur] += dp[cur][i]; } } } sc_down[cur] += num_down[cur] * (num_down[cur] - 1) / 2; sc_up[cur] += num_up[cur] * (num_up[cur] - 1) / 2; return Math.max(ret, Math.max(sc_down[cur], sc_up[cur])); } int N; void solve() { Scanner sc = new Scanner(System.in); N = sc.nextInt(); A = new int[N]; for (int i = 0; i < 50000; i++) edges[i] = new ArrayList<>(); for (int i = 0; i < 1000; i++) for (int j = 0; j < 50000; j++) dp[i][j] = -1; for (int i = 0; i < N; i++) A[i] = sc.nextInt(); for (int i = 0; i < N - 1; i++) { int x = sc.nextInt() - 1; int y = sc.nextInt() - 1; edges[x].add(y); edges[y].add(x); } int ret = dfs(0, -1); System.out.println(ret); } }