评测记录

#include <iostream>
#include <vector>
using namespace std;
const int kMaxN=1e5+1;
struct SLPF
{
  int size,father,top,heavyson,deep,where;
}s[kMaxN*2];
vector<int>v[kMaxN];//把每个颜色为i的点的dfs序按顺序存下来，二分查找要用
int n,m,t[kMaxN];
struct EDGE
{
  int to,nt;
}e[kMaxN*2];
int cnt,hd[kMaxN];
int num,b[kMaxN];
void Add(int a,int b)
{
  e[++cnt].to=b;
  e[cnt].nt=hd[a];
  hd[a]=cnt;
}
void dfs1(int now,int last)//模板不解释
{
  s[now].deep=s[last].deep+1;
  s[now].father=last;
  s[now].size=1;
  int maxs=0;
  for(int i=hd[now];i;i=e[i].nt)
  {
    if(e[i].to==last)continue;
    dfs1(e[i].to,now);
    s[now].size+=s[e[i].to].size;
    if(s[e[i].to].size>maxs)
    {
      maxs=s[e[i].to].size;
      s[now].heavyson=e[i].to;
    }
  }
}
void dfs2(int now,int top)
{
  s[now].top=top;
  s[now].where=++num;
  b[num]=now;
  if(!s[now].heavyson)return;
  dfs2(s[now].heavyson,top);
  for(int i=hd[now];i;i=e[i].nt)
  {
    if(e[i].to==s[now].father||e[i].to==s[now].heavyson)continue;
    dfs2(e[i].to,e[i].to);
  }
}
bool Ask(int ll,int rr,int c)//查找有没有颜色为c的点dfs序在ll和rr之间（也就是这条链上）
{
  if(v[c].empty())return false;
  int l=0,r=v[c].size();
  while(l<=r)
  {
    int mid=(l+r)/2;
    if(v[c][mid]>=ll&&v[c][mid]<=rr)
    {
      return true;
    }
    if(v[c][mid]<ll)l=mid+1;
    else r=mid-1;
  }
  return false;
}
bool Check(int x,int y,int c)//跳链
{
  while(s[x].top!=s[y].top)
  {
    if(s[s[x].top].where<s[s[y].top].where)
    {
      swap(x,y);
    }
    if(Ask(s[s[x].top].where,s[x].where,c))return true;
    x=s[s[x].top].father;
  }
  if(s[x].where>s[y].where)swap(x,y);
  return Ask(s[x].where,s[y].where,c);
}
signed main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
  cin>>t[i];
}
for(int i=1;i<n;i++)
{
  int x,y;
  cin>>x>>y;
  Add(x,y);
  Add(y,x);
}
dfs1(1,0);
dfs2(1,1);
for(int i=1;i<=num;i++)
{
  v[t[b[i]]].push_back(i);
}
for(int i=1;i<=m;i++)
{
  int x,y,z;
  cin>>x>>y>>z;
  cout<<Check(x,y,z);
}
return 0;
}