#include <iostream>//
#include <cstring>//
#include <algorithm> //这里可以扩展到很多种颜色
#include<queue>
using namespace std;
const int N=200010,M=2*N;
int depth[N];
int fa[N][18];
int st[N][18];//二进制压缩一下 返回的是 往上跳多少次的路径中颜色 的状态 跟lca对应
int n,m;
char cow[N];
int h[N],e[M],ne[M],idx;
int get_cow(char c)
{
return c=='G'?1:2;//是G就是1 否则就是2
}
void add(int a,int b)
{
e[idx]=b;ne[idx]=h[a];h[a]=idx++;
}
// void bfs(int root)
// {
// queue<int>q;
// q.push(root);
// memset(depth,0x3f,sizeof depth);
// depth[root]=1,depth[0]=0;
// while(q.size())
// {
// auto t=q.front();
// q.pop();
// for(int i=h[t];~i;i=ne[i])
// {
// int j=e[i];
// if(depth[j]>depth[t]+1)
// {
// depth[j]=depth[t]+1;
// q.push(j);
// fa[j][0]=t;
// st[j][0]=get_cow(cow[t]);//往上走的状态不包括自己哦 没让你传编号 应该是编号对应的牛压
// for(int k=1;k<=17;k++)
// {
// fa[j][k]=fa[fa[j][k-1]][k-1];
// st[j][k]=(st[fa[j][k-1]][k-1]|st[j][k-1]);//路径压缩的状态都要压加上 类比归类比 你别连里面放st啊
// }
// }
// }
// }
// }
int lca(int a,int b)//返回的是 相连接的路径上 颜色的状态
{
if(depth[a]<depth[b]) swap(a,b);
int state = (get_cow(cow[a]) | get_cow(cow[b]));//tql 妙呀 st只能查路径走的状态 不包括这个点的状态 这里包含上就可以了 正准备问
//如果自身就是那个颜色的话 路径没有的话怎么办呢
for(int k=17;k>=0;k--)
{
if(depth[fa[a][k]]>=depth[b])
{
state|=st[a][k];
a=fa[a][k];
}
}
if(a==b) return state;
for(int k=17;k>=0;k--)
{
if(fa[a][k]!=fa[b][k])
{
state|=st[a][k];
state|=st[b][k];
a=fa[a][k];
b=fa[b][k];
}
}
state|=st[a][0];
return state;
}
int main()
{
memset(h,-1,sizeof h);
cin>>n>>m;
cin>>cow+1;
for(int i=0;i<n-1;i++)
{
int a,b;
cin>>a>>b;
add(a,b),add(b,a);
}
bfs(1);//1节点当根节点 预处理depth 和st
while(m--)
{
int a,b;
char c;
cin>>a>>b>>c;
int p=get_cow(c);//给你牛了 给我搞出来状态
if(lca(a,b)&p) //让你看状态呢 天天用编号个猫心啊毛线
cout<<1;
else cout<<0;
}
return 0;
}
用到了状态压缩 tql 5个类型的牛都能给你判断出来