1 #include <cstdio>  2 #include <cstring>  3 #include <algorithm>  4 #include <iostream>  5 #include <queue>  6 #include <cmath>  7 #include <map>  8 #include <vector>  9 using namespace std; 10 #define N 80010 11 #define M 30010 12 struct node 13 { 14     int u, v, next; 15 }edge[N*2]; 16 struct P 17 { 18     int u, v, next, num, k, lca; 19 }Edge[M*2]; 20 int n, m, tot, Tot, head[N], Head[N], a[N], fa[N], dis[N]; 21 bool vis[N]; 22 vector<int> vec; 23  24 void init() 25 { 26     tot = Tot = 0; 27     memset(head, -1, sizeof(head)); 28     memset(Head, -1, sizeof(Head)); 29     memset(dis, -1, sizeof(dis)); 30     memset(vis, false, sizeof(vis)); 31     for(int i = 1; i <= n; i++) fa[i] = i; 32 } 33  34 void add(int u, int v) 35 { 36     edge[tot].u = u; edge[tot].v = v; edge[tot].next = head[u]; head[u] = tot++; 37 } 38  39 void Add(int u, int v, int k) 40 { 41     Edge[Tot].k = k; Edge[Tot].u = u; Edge[Tot].v = v; Edge[Tot].next = Head[u]; Edge[Tot].num = 0; Edge[Tot].lca = -1; Head[u] = Tot++; 42 } 43  44 int Find(int x) 45 { 46     while(x != fa[x]) x = fa[x]; 47     return x; 48 } 49  50 void Merge(int u, int v) 51 { 52     u = Find(u), v = Find(v); 53     fa[v] = u; 54 } 55  56 void tarjan(int u) 57 { 58     vis[u] = true; 59     for(int i = head[u]; ~i; i = edge[i].next) { 60         int v = edge[i].v; 61         if(!vis[v]) { 62             dis[v] = dis[u] + 1; 63             tarjan(v); 64             fa[v] = u; 65         } 66     } 67     for(int i = Head[u]; ~i; i = Edge[i].next) { 68         int v = Edge[i].v, k = Edge[i].k; 69         if(vis[v]) { 70             int ff = Find(v); 71             if(k) { 72                 Edge[i].num = Edge[i^1].num = dis[u] + dis[v] - 2 * dis[ff]; 73                 Edge[i].lca = Edge[i^1].lca = ff; 74             } 75             else a[u] = v; 76         } 77     } 78 } 79  80 int doit(int u, int v, int k, int num, int lca) 81 { 82     vec.clear(); 83     while(u != lca) { 84         vec.push_back(a[u]); u = fa[u]; 85     } 86     while(v != lca) { 87         vec.push_back(a[v]); v = fa[v]; 88     } 89     vec.push_back(a[lca]); 90     sort(vec.begin(), vec.end()); 91     num++; 92     return vec[num-k]; 93 } 94  95 void solve() 96 { 97     for(int i = 0; i < Tot; i += 2) { 98         int u = Edge[i].u, v = Edge[i].v, k = Edge[i].k, num = Edge[i].num, lca = Edge[i].lca; 99         if(k) {100             if(num + 1 < k) puts("invalid request!");101             else printf("%d\n", doit(u, v, k, num, lca));102         }103     }104 }105 106 int main()107 {108     scanf("%d%d", &n, &m);109     init();110     for(int i = 1; i <= n; i++) scanf("%d", a+i);111     for(int i = 1; i < n; i++) {112         int u, v;113         scanf("%d%d", &u, &v);114         add(u, v); add(v, u);115     }116     for(int i = 0; i < m; i++) {117         int u, v, k;118         scanf("%d%d%d", &k, &u, &v);119         Add(u, v, k); Add(v, u, k);120     }121     dis[1] = 0;122     tarjan(1);123     solve();124     return 0;125 }