题意:给出一棵点权树，多次询问从一个点u走到另一个点v的路径中，第一个点权不小于w的点是什么

用lct就可以水过去了。。。

Portal 我只有数据。。。

#include <math.h>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

#define g() getchar()
template<class Q>void Scan(Q&x){
	char c;int f=1;
	while(c=g(),c<48||c>57)if(c=='-')f=-1;
	for(x=0;c>47&&c<58;c=g())x=10*x+c-48;
	x*=f;
}

#define Max(x,y) if(x<y)x=y
#define rep(i,a,b) for(int i=a;i<b;++i)

const int MAXN=2e5+5;

typedef struct node*star;

struct node{
	int x,mx;
	bool rev;
	star ch[2],p;
	inline int d(){
		rep(i,0,2)
			if(p->ch[i]==this)return i;
		return -1;
	}
	inline void set_ch(star x,int d){
		if(~d)ch[d]=x; x->p=this;
	}
	inline void update();
	inline void down(){
		if(!rev)return;
		swap(ch[0],ch[1]);
		ch[0]->rev^=1,ch[1]->rev^=1;
		rev=0;
	}
}pool[MAXN];
star tail=pool;
inline star null(){
	star x=tail++;
	x->ch[0]=x->ch[1]=x->p=x;
	return x;
}
star nu=null();

inline void node::update(){
	mx=x;
	rep(i,0,2)
		if(ch[i]!=nu)Max(mx,ch[i]->mx);
}

inline void rot(star x){
	star y=x->p;
	int d=x->d();
	y->p->set_ch(x,y->d());
	y->set_ch(x->ch[d^1],d),y->update();
	x->set_ch(y,d^1);
}

void pd(star x){
	if(~x->d())pd(x->p); x->down();
}

inline void splay(star x){
	pd(x);
	for(int d1,d2;~(d1=x->d());rot(x))
		if(~(d2=x->p->d()))rot(d1^d2?x:x->p);
	x->update();
}

inline void Access(star x){
	star y=x,t=nu;
	for(;x!=nu;t=x,x=x->p){
		splay(x);
		x->ch[1]=t,x->update();
	}
	splay(y);
}

inline void Evert(star x){
	Access(x),x->rev^=1;
}

inline int Query(star x,star y,int w){
	Evert(x),Access(y);
	if(y->mx<w)return -1;
	while(y!=nu){
		y->down();
		if(y->ch[0]!=nu&&y->ch[0]->mx>=w)
			y=y->ch[0];
		else{
			if(y->x>=w)break;
			y=y->ch[1];	
		}
	}
	return y-pool;
}

int n,q;

struct edge{
	int t,n;
	edge(int t=0,int n=0):t(t),n(n){}
}e[MAXN<<1];
int head[MAXN],tot;
inline void AddEdge(int s,int t){
	e[++tot]=edge(t,head[s]),head[s]=tot;
	e[++tot]=edge(s,head[t]),head[t]=tot;
}

star p[MAXN];

void dfs(int x,int par=0){
	for(int i=head[x],y;i;i=e[i].n)
		if((y=e[i].t)!=par){
			p[y]->p=p[x];
			dfs(y,x);
		}
}

inline void Init(){
	Scan(n),Scan(q);
	rep(i,1,n+1){
		p[i]=tail++;
		*p[i]=*nu;
		Scan(p[i]->x);
		p[i]->mx=p[i]->x;
	}
	rep(i,1,n){
		int x,y;
		Scan(x),Scan(y);
		AddEdge(x,y);
	}
	dfs(1);
}

inline void Solve(){
	rep(i,0,q){
		int u,v,w;
		Scan(u),Scan(v),Scan(w);
		int res=Query(p[u],p[v],w);
		if(~res)printf("%d\n",res);
		else puts("sad");
	}
}

int main(){
	freopen("db.txt","r",stdin);
	freopen("st.out","w",stdout);
	Init(); Solve(); return 0;
}
/*
	4 2
	1 2 1 2
	1 2
	2 3
	3 4
	1 4 2
	3 4 2
*/