不知道是常数大还是做法错了还是输入挂了,难绷
#include<bits/stdc++.h>
#define endl '\n'
#define debug(x) cout<<#x<<':'<<x<<endl
using namespace std;
const int N=1e5+5;
int n,m,cnt;
int top[N],son[N],dep[N],siz[N],fa[N],dfn[N],a[N],num[N],tot;
int to[N<<1],nxt[N<<1],head[N<<1];
#define ls p<<1
#define rs p<<1|1
struct node{
int l,r;
set<int> s;
}tree[N<<2];
void build(int p,int l,int r){
tree[p].l=l,tree[p].r=r;
for(int i=l;i<=r;i++) tree[p].s.insert(a[i]);
if(l==r) return;
int mid=(l+r)>>1;
build(ls,l,mid);
build(rs,mid+1,r);
}
int ask(int p,int l,int r,int k){
if(l<=tree[p].l&&tree[p].r<=r){
return tree[p].s.count(k);
}
int mid=(tree[p].l+tree[p].r)>>1,res=0;
if(l<=mid) res+=ask(ls,l,r,k);
if(r>mid) res+=ask(rs,l,r,k);
return res;
}
void add(int x,int y){
to[++tot]=y;
nxt[tot]=head[x];
head[x]=tot;
}
void dfs1(int x,int f){
siz[x]=1;dep[x]=dep[f]+1;fa[x]=f;
int mx=INT_MIN;
for(int i=head[x];i;i=nxt[i]){
int y=to[i];
if(y==f) continue;
dfs1(y,x);
siz[x]+=siz[y];
if(siz[y]>mx)mx=siz[y],son[x]=y;
}
}
void dfs2(int x,int hd){
top[x]=hd;
dfn[x]=++cnt;
a[cnt]=num[x];
if(son[x]) dfs2(son[x],hd);
for(int i=head[x];i;i=nxt[i]){
int y=to[i];
if(y!=son[x]&&y!=fa[x]) dfs2(y,y);
}
}
int query(int x,int y,int k){
while(top[x]^top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
if(ask(1,dfn[top[x]],dfn[x],k)>0) return 1;
x=fa[top[x]];
}
if(dfn[x]>dfn[y]) swap(x,y);
return ask(1,dfn[x],dfn[y],k);
}
signed main(){
while(scanf("%d%d",&n,&m)!=EOF){
memset(top,0,sizeof(top));
memset(son,0,sizeof(son));
memset(dep,0,sizeof(dep));
memset(siz,0,sizeof(siz));
memset(fa,0,sizeof(fa));
memset(dfn,0,sizeof(dfn));
memset(a,0,sizeof(a));
memset(num,0,sizeof(num));
memset(to,0,sizeof(to));
memset(head,0,sizeof(head));
memset(nxt,0,sizeof(nxt));
tot=cnt=0;
for(int i=1;i<=(n<<2);i++){
tree[i].l=tree[i].r=0;
tree[i].s.clear();
}
for(int i=1;i<=n;i++) cin>>num[i];
for(int i=1,u,v;i<n;i++){
cin>>u>>v;
add(u,v),add(v,u);
}
dfs1(1,0);
dfs2(1,1);
build(1,1,n);
for(int i=1,x,y,k;i<=m;i++){
cin>>x>>y>>k;
cout<<(query(x,y,k)?"Find\n":"NotFind\n");
}
}
return 0;
}