小美的美丽树

import java.util.*;

public class Main{
    static int max=0,index=0;//最大差值，最大差值对应的最小编号
    static int[][] dp;//dp[i][0/1/2]i为根对应的最大值、最小值,节点数量
    static int k=0;
    public static void main(String[] argvs){
        Scanner in=new Scanner(System.in);
        int n=in.nextInt();
        k=in.nextInt();
        int[] v=new int[n+1];
        dp=new int[n+1][3];
        
        for(int i=1;i<=n;i++) {
            v[i]=in.nextInt();
            //dp[i][1]=Integer.MAX_VALUE;
        }
        Map<Integer,Set<Integer>> g=new HashMap<>();
        for(int i=0;i<n-1;i++){
            int x=in.nextInt(),y=in.nextInt();
            Set<Integer> s1=g.computeIfAbsent(x,(a)->new HashSet<>());
            Set<Integer> s2=g.computeIfAbsent(y,(a)->new HashSet<>());
            s1.add(y);
            s2.add(x);
        }
        
        int r=in.nextInt();
        dfs(r,g,v);
        System.out.print(index);
        
        
           
    }
    
    public static void dfs(int cur,Map<Integer,Set<Integer>> g,int[] v){
        dp[cur][0]=v[cur];
        dp[cur][1]=v[cur];
        dp[cur][2]=1;
        if(!g.containsKey(cur) || g.get(cur).size()==0) return;
        Set<Integer> son=g.get(cur);
        for(int s:son){
            Set<Integer> tmp=g.get(s);
            tmp.remove(cur);
            dfs(s,g,v);
            dp[cur][0]=Math.max(dp[cur][0],dp[s][0]);
            dp[cur][1]=Math.min(dp[cur][1],dp[s][1]);
            dp[cur][2]+=dp[s][2]; 
        }
        int dis=dp[cur][0]-dp[cur][1];
        if(dp[cur][2]<=k){
            if(dis>max){
                max=dis;
                index=cur;
            }else if(max==dis){
                index=Math.min(index,cur);
            }
        } 
        
        
        
    }
}

import java.util.*;
import java.io.*;

public class Main{
    static int poor ; //记录在递归过程中出现的符合要求最大差值
    static int index ;//最大差值的下标
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] one = br.readLine().trim().split(" ");
        int n = Integer.parseInt(one[0]);
        int k = Integer.parseInt(one[1]);
        String[] value = br.readLine().trim().split(" ");
        Node[] nodes = new Node[n]; //节点数组
        //构造节点
        for(int i = 0; i < n ; i++){
            int num = Integer.parseInt(value[i]);
            nodes[i] = new Node(num, i + 1 ,new ArrayList<Node>());
        }
        //把节点连接起来
        for(int i = 0; i < n - 1; i++){
            String[] line = br.readLine().trim().split(" ");
            int n1 = Integer.parseInt(line[0]);
            int n2 = Integer.parseInt(line[1]);
            nodes[n1 - 1].list.add(nodes[n2 - 1]);
            nodes[n2 - 1].list.add(nodes[n1 - 1]);
        }
        poor = 0;
        index = -1;
        Node node = nodes[Integer.parseInt(br.readLine()) - 1];//根节点
        //遍历根节点
        for(Node nn : node.list){
            dfs(nn, node, k);
        }
        System.out.println(index);
    }
    public static Info dfs(Node node,Node father,int k){
        int maxS = node.value;
        int minS = node.value;
        int flo = 1;//node节点中个数，flo = 1 是 node这个1
        for(Node n : node.list){//遍历连接点
            if(n != father){//父节点不遍历
                Info info = dfs(n, node, k);
                flo += info.flo;//子树中个数相加
                maxS = Math.max(maxS, info.max);
                minS = Math.min(minS, info.min);
            }
        }
        //如果节点个数小于等于k，并且最大值和最小值差比最大差大，那么替换
        if(flo <= k && poor < maxS - minS){
            poor =  maxS - minS;
            index = node.index;
        }
        //如果节点个数小于等于k，并且最大值和最小值差等于最大差而且下标更小，那么替换下标
        if( flo <= k && poor == maxS - minS && node.index < index){
            index = node.index;
        }
        return new Info(maxS, minS, flo);
    }
}
//子树返回的信息
class Info{
    int max;//子树中的最大值
    int min;//子树中的最小值
    int flo;//子树中节点个数（在确定根节点的情况下）
    public Info(int max, int min, int flo){
        this.max = max;
        this.min = min;
        this.flo = flo;
    }
}
//节点类
class Node{
    int value;//权值
    int index;//节点的下标
    List<Node> list;//连接的点
    public Node(int value,  int index, List<Node> list){
        this.value = value;
        this.index = index;
        this.list = list;
    }
}