import java.util.*;
import java.io.*;
import java.math.BigInteger;

public class Problem
{

    static int mod = (int) (1e9+7);
    static InputReader in;
    static PrintWriter out;
    static int[] rt;
    static int[] size;

    static void initialize(int n){
        rt = new int[n + 1];
        size = new int[n + 1];
        for(int i = 0; i < rt.length; i++){
            rt[i] = i;
            size[i] = 1;
        }
    }
    
    static int root(int x){
        while(rt[x] != x){
            rt[x] = rt[rt[x]];
            x = rt[x];
        }
        return x;
    }
    
    static long union(int x,int y){
        int root_x = root(x);
        int root_y = root(y);
        if(root_x == root_y) return 0;
        long val = size[root_x] *1l* size[root_y];
        if(size[root_x]<size[root_y]){
            rt[root_x] = rt[root_y];
            size[root_y] += size[root_x];
        }
        else{
            rt[root_y] = rt[root_x];
            size[root_x] += size[root_y];            
        }
        
        return val;
    }
    
    static void solve()
    {
        in = new InputReader(System.in);
        out = new PrintWriter(System.out);            
        
        int t = 1;
        
        while(t-- > 0){
            int n = in.nextInt();
            int[] arr = in.nextIntArray(n);
            ArrayList<Pair> list = new ArrayList<>();
            
            for(int i = 1; i < n; i++){
                int u = in.nextInt() - 1;
                int v = in.nextInt() - 1;
                list.add(new Pair(u, v, Math.max(arr[u],arr[v])));
            }
            list.sort((p1,p2) -> Integer.compare(p1.i, p2.i));
            initialize(n);
            long s1 = 0;
            for(int i = 0; i < list.size(); i++){
                s1 += union(list.get(i).x, list.get(i).y) * list.get(i).i;
            }
            for(int i = 0; i < list.size(); i++){
                Pair p = list.get(i);
                p.i = Math.min(arr[p.x],arr[p.y]);
            }
            list.sort((p1,p2) ->... What is the time complexity of the previous code?