Revise paste Untitled

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <queue>
//#include <bits/stdc++.h>

using namespace std;
const int INF = 2e9;
const int maxn = 3e5 + 10;
typedef long long ll;
int n;
ll k;
vector<int> graph[maxn];
int a[maxn];
void brute_force() {
    int S = 0;

for(int i = 0; i < k; i++) {
        vector<bool> visited(n + 1, false);
        visited[S] = true;
        queue<int> q;
        q.push(S);
        q.push(0);
        int max_dist = -INF;
        int next_node = -1;
        while(!q.empty()) {
            int node = q.front();
            q.pop();
            int dist = q.front();
            q.pop();
            if(a[node] - dist > max_dist and S != node) {
                max_dist = a[node] - dist;
                next_node = node;
            }
            if(a[node] - dist == max_dist and S != node) {
                next_node = min(next_node, node);
            }
            for(int neighbour : graph[node]) {
                if(!visited[neighbour]) {
                    visited[neighbour] = true;
                    q.push(neighbour);
                    q.push(dist + 1);
                }
            }
        }
        S = next_node;
        
    }
    cout << S + 1 << endl;
}
void solve_subtask2() {
    int S = 0;
    vector<int> cnt(n + 1, 0);
    vector<int> cycle;
    bool cycle_begin = false;
    int till_cycle = 0;
    for(int i = 0; i < 10000; i++) {
        
        vector<bool> visited(n + 1, false);
        visited[S] = true;
        int next_node = -1, max_dist = -INF;
        
        queue<int> q;
        q.push(S);
        q.push(0);
        cnt[S]++;
        if(cnt[S] == 2) {
            cycle_begin = true;
//            cout << S + 1 << endl;
        }
        
        if(cycle_begin) {
            cycle.push_back(S);
        }
        else {
            till_cycle++;
        }
        while(!q.empty()) {
            int node = q.front();
            q.pop();
            int dist = q.front();
            q.pop();
            
            if(a[node] - dist > max_dist and S != node) {
                max_dist = a[node] - dist;
                next_node = node;
            }
            if(a[node] - dist == max_dist and S != node) {
                next_node = min(next_node, node);
            }
            for(int neighbour : graph[node]) {
                if(!visited[neighbour]) {
                    visited[neighbour] = true;
                    q.push(neighbour);
                    q.push(dist + 1);
                }
            }
        }
        S = next_node;
        if(cycle_begin and S == cycle[0]) {
//            for(int x : cycle) {
//                cout << x + 1 << " " ;
//            }
            break;
        }
    }
//    cout << endl;
//    cout << "till: " << till_cycle - cycle.size() - 1<< endl;
//    cout << cycle.size() << endl;
    till_cycle =  till_cycle - cycle.size() - 1;
    k -= till_cycle;
//    cout << k << endl;
    
    cout << cycle[(k + 1) % (ll) cycle.size()] + 1 << endl;
}
int main()
{
    ios::sync_with_stdio(false);
    cin >> n >> k;
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }
    
    for(int i = 1; i < n; i++) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    
    if(n <= 1000 and k <= 1000) {
        brute_force();
        return 0;
    }
    
    if(n <= 1000) {
        solve_subtask2();
        return 0;
    }
    return 0;
}