70pts求调

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define lson (p<<1)
#define rson (p<<1|1)
#define mid (l+r>>1)
const int N = 7e5+15;
const int INF = 2e9+1;
inline int read(){
	int x=0;char c=getchar();
	while(c<'0'||c>'9')c=getchar();
	while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x;
}
int n,q,x,y,a[N],fa[N],dep[N],top[N],siz[N],id[N],son[N];
vector<int>v[N];
int tr[N<<2],b[N],idx;
struct node{
	int l,r;
}st[N];
int tot,c[N];
void dfs(int p,int fath){
	fa[p] = fath;dep[p] = dep[fath]+1;
	siz[p] = 1;
	for(int i = 0;i < v[p].size();++i){
		if(v[p][i]==fath)continue;
		dfs(v[p][i],p);
		siz[p]+=siz[v[p][i]];
		if(siz[v[p][i]]>siz[son[p]])son[p]=v[p][i];
	}
}
void dfs1(int p){
	id[p]=++idx;b[idx]=a[p];c[idx]=p;
	if(son[p]){
		top[son[p]] = top[p];
		dfs1(son[p]);
	}
	for(int i = 0;i < v[p].size();++i){
		if(v[p][i]==fa[p]||v[p][i]==son[p])continue;
		top[v[p][i]]=v[p][i];
		dfs1(v[p][i]);
	}
}
void build(int p,int l,int r){
	if(l == r){tr[p]=b[l];return;}
	build(lson,l,mid);
	build(rson,mid+1,r);
	tr[p] = min(tr[lson],tr[rson]);
}
int query1(int p,int l,int r,int sl,int sr,int k){
	if(sl>sr||tr[p]>k)return n+1;
	if(l == r)return l;
	int cnt1=n+1;
	if(sr >mid&&tr[rson]<=k)cnt1 = query1(rson,mid+1,r,sl,sr,k);
	if(cnt1!=n+1)return cnt1;
	if(sl<=mid&&tr[lson]<=k)return query1(lson,l,mid,sl,sr,k);
	return n+1;
}
int query2(int p,int l,int r,int sl,int sr,int k){
	if(sl>sr||tr[p]>k)return n+1;
	if(l == r)return l;
	int cnt1=n+1;
	if(sl<=mid&&tr[lson]<=k)cnt1 = query2(lson,l,mid,sl,sr,k);
	if(cnt1!=n+1)return cnt1;
	if(sr >mid&&tr[rson]<=k)return query2(rson,mid+1,r,sl,sr,k);
	return n+1; 
}
void solve(int u,int v,int ans){
	int mod=0,x1;
	while(top[u]!=top[v]){
		if(dep[top[u]]>=dep[top[v]]){
			x1 = id[u]+1;mod=0;
			while(mod!=INF){
				x1 = query1(1,1,n,id[top[u]],x1-1,ans);
				mod = b[x1];
				ans%=mod;
			}
			u=fa[top[u]];
		}else {
			st[++tot]=node{id[top[v]],id[v]};
			v=fa[top[v]];
		}
	}
	if(dep[u]>=dep[y]){
		mod=0;
		x1 = id[u]+1;
		while(mod!=INF){
			x1 = query1(1,1,n,id[v],x1-1,ans);
			mod = b[x1];
			ans%=mod;
		}
	}else {
		st[++tot]=node{id[u],id[v]};
	}
	while(tot){
		mod = 0;x1 = st[tot].l-1;
		while(mod != INF){
			x1 = query2(1,1,n,x1+1,st[tot].r,ans);
			mod = b[x1];
			ans %= mod;
		}
		--tot;
	}
	printf("%d\n",ans);
}
int main(){
	n=read(),q=read();
	b[n+1]=INF;b[0]=INF;
	for(int i = 1;i < n;++i){
		x=read(),y=read();
		v[x].push_back(y);
		v[y].push_back(x);
	}
	for(int i = 1;i <= n;++i)a[i]=read();
	dfs(1,0);
	top[1] = 1;
	dfs1(1);
	build(1,1,n);
	int k;
	while(q--){
		x=read(),y=read(),k=read();
		solve(x,y,k);
	}
	return 0;
}