求助SP11985

#include<algorithm>
#include<iostream>
#include<string.h>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#include<map>
#include<set>
using namespace std;
#define lb(a,b,n) (lower_bound((a)+1,(a)+(n)+1,(b))-(a))
#define repu(i,u) for(int i=(h[u]);i;i=(ne[i]))
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dwn(i,a,b) for(int i=(a);i>=(b);i--)
#define pb(a) push_back((a))
#define inf 0x3f3f3f3f
#define llinf 1e18
#define debug cout<<"wwwwww"<<endl
#define xx return
const int N=1e5+10;

int n,m;
int c[N],wt[N];
int h[N],e[N*2],ne[N*2],idx;
vector<int>val[N];

namespace xx_CTT{
	int d[N],son[N],sizt[N],fa[N];
	int id[N],top[N],cnt;
	void dfs1(int u,int fath){
		fa[u]=fath;d[u]=d[fath]+1;sizt[u]=1;
		int max_son=-1;
		repu(i,u){
			int v=e[i];
			if(v==fath)continue;
			dfs1(v,u);
			sizt[u]+=sizt[v];
			if(sizt[v]>max_son)son[u]=v,max_son=sizt[v];
		}
	}
	void dfs2(int u,int topf){
		id[u]=++cnt;wt[cnt]=u;top[u]=topf;
		if(!son[u])xx;
		dfs2(son[u],topf);
		repu(i,u){
			int v=e[i];
			if(v==fa[u]||v==son[u])continue;
			dfs2(v,v);
		}
	}
	int ask(int u,int v,int k){
		while(top[u]!=top[v]){
			
			if(d[top[u]]<d[top[v]])swap(u,v);
			vector<int>::iterator it=lower_bound(val[k].begin(),val[k].end(),id[top[u]]);
			if(it!=val[k].end()&&*it<=id[u]){xx 1;}
			u=fa[top[u]];
		}
		if(d[u]>d[v])swap(u,v);
		vector<int>::iterator it=lower_bound(val[k].begin(),val[k].end(),id[u]);
		if(it!=val[k].end()&&*it<=id[v]){xx 1;}
		xx 0;
	}
}

namespace Main_xx{
	void add(int a,int b){e[++idx]=b,ne[idx]=h[a],h[a]=idx;}
	void Main(){
		while(scanf("%d%d",&n,&m)!=EOF){
			memset(h,0,sizeof h);
			idx=0;
			rep(i,1,n){
				xx_CTT::son[i]=0;
				xx_CTT::id[i]=0;
				wt[i]=0;
			}
			rep(i,1,n){cin>>c[i];c[i]++;}
			rep(i,1,n-1){int u,v;cin>>u>>v;add(u,v);add(v,u);}
			xx_CTT::dfs1(1,0);
			xx_CTT::dfs2(1,1);
			rep(i,1,xx_CTT::cnt){
				val[c[wt[i]]].pb(i);
			}
			while(m--){
				int u,v,c;
				cin>>u>>v>>c;
				c++;
				if(xx_CTT::ask(u,v,c))cout<<"Find"<<endl;
				else cout<<"NotFind"<<endl;
			}
			rep(i,1,xx_CTT::cnt){
				val[c[wt[i]]].clear();
			}	
		}xx;	
	}
}

signed main(){
//	ios::sync_with_stdio(0);
//	cin.tie(0);cout.tie(0);
	Main_xx::Main();
	xx 0;
}