#include<bits/stdc++.h>
using namespace std;
const int mx=200025;
struct node
{
int sum;
node* l;
node* r;
};
typedef node* pnode;
pnode roots[mx];
int rc[mx];
int re[mx];
int cost[mx];
vector v[mx];
int par[22][mx];
int depth[mx];
int n;
static int uget()
{
int c;
while(c = getchar(), isspace©) {}
int n = c - ‘0’;
while(c = getchar(), isdigit©) { n = n * 10 + (c - ‘0’); }
return n;
}
template static void uput(T n)
{
char s[30];
int x = 0;
do { s[x ++]=(n % 10) + ‘0’; n /= 10; } while(n);
for(int i = x - 1; i >= 0; i --) putchar(s[i]);
putchar(’\n’);
}
int get(pnode h)
{
if(h==NULL)
return 0;
else
return h->sum;
}
pnode init(int value)
{
pnode t=(pnode)malloc(sizeof(node));
t->l=NULL;
t->r=NULL;
t->sum=value;
return t;
}
pnode add(pnode &root,int l,int r,int cst,int val)
{
if(!root)
{
root=init(0);
}
if(l==r)
{
return init(val+get(root));
}
pnode p=init(0);
int mid=(l+r)/2;
if(cst<=mid)
{
p->l=add(root->l,l,mid,cst,val);
p->r=root->r;
}
else
{
p->r=add(root->r,mid+1,r,cst,val);
p->l=root->l;
}
p->sum=get(p->l)+get(p->r);
return p;
}
int get(pnode &a,pnode&b,pnode &lca,pnode &plca,int l,int r,int k)
{
if(l==r)
{
if(!a)
a=init(0);
if(!b)
b=init(0);
if(!lca)
lca=init(0);
if(!plca)
plca=init(0);
return get(a)+get(b)-get(lca)-get(plca);
}
if(!a)
a=init(0);
if(!b)
b=init(0);
if(!lca)
lca=init(0);
if(!plca)
plca=init(0);
int mid=(l+r)/2;
if(k<=mid)
return get(a->l,b->l,lca->l,plca->l,l,mid,k);
else
return get(a->r,b->r,lca->r,plca->r,mid+1,r,k);
}
void dfs(int node,int p)
{
par[0][node]=p;
for(int ii=0;ii<(int)v[node].size();ii++)
{
int i=v[node][ii];
if(i==p)
continue;
int uu=re[i];
roots[i]=add(roots[node],0,n,uu,1);
depth[i]=depth[node]+1;
dfs(i,node);
}
}
int LCA(int a,int b)
{
if(depth[a]<depth[b])
swap(a,b);
for(int i=19;i>=0;i–)
if(depth[a]-(1 << i)>=depth[b])
a=par[i][a];
if(a==b)
return a;
for(int i=19;i>=0;i–)
if(par[i][a]!=-1&&par[i][a]!=par[i][b])
{
a=par[i][a];
b=par[i][b];
}
return par[0][a];
}
int main()
{
int m,i,u;
int ca=0;
while(scanf("%d%d",&n,&m)!=EOF)
{
if(ca>0)
printf("\n");
ca++;
for(i=1;i<=n;i++)
{
v[i].clear();
}
for(i=0;i<=n;i++)
{
delete roots[i];
}
for(i=0;i<n;i++)
{
u=uget();
re[i+1]=u;
}
int s,t;
for(i=0;i<n-1;i++)
{
s=uget();
t=uget();
v[s].push_back(t);
v[t].push_back(s);
}
roots[0]=init(0);
roots[1]=add(roots[0],0,n,re[1],1);
dfs(1,-1);
for(int i=1;i<20;i++)
{
for(int j=1;j<=n;j++)
{
if(par[i-1][j]!=-1)
par[i][j]=par[i-1][par[i-1][j]];
}
}
while(m–)
{
int k;
s=uget();
t=uget();
k=uget();
int lca=LCA(s,t);
int oo=get(roots[s],roots[t],roots[lca],lca==1 ? roots[0] : roots[par[0][lca]],0,n,k);
if(oo==0)
{
printf(“NotFind\n”);
}
else
{
printf(“Find\n”);
}
}
}
}https://www.spoj.com/problems/GOT/