rt40分QwQ

#include<iostream>
using namespace std;
struct EDGE{
	int u,v,nxt;
}ed[2000002];
int n,m,tot=0,head[1000002],fa[1000002][22],gcow[1000002][22],hcow[1000002][22],dep[1000002];
string s;
void add_edge(int u,int v)
{
	ed[++tot]={u,v,head[u]};
	head[u]=tot;
}
void DFS_init(int x)//边，vv相当于当前节点 
{
	int i,uu=ed[x].u,vv=ed[x].v;
	fa[vv][0]=uu;dep[vv]=dep[uu]+1;
	if(uu-1>=0) s[uu-1]=='G'?gcow[vv][0]=1:hcow[vv][0]=1;
	for(i=1;i<=20;i++)
	{
		fa[vv][i]=fa[fa[vv][i-1]][i-1];
		gcow[vv][i]=gcow[vv][i-1]||gcow[fa[vv][i-1]][i-1];
		hcow[vv][i]=hcow[vv][i-1]||hcow[fa[vv][i-1]][i-1];
	}
	for(i=head[vv];i>0;i=ed[i].nxt)
	{
		if(ed[i].v!=uu) DFS_init(i);
	}
	return ;
}
bool get_LCA(int u,int v,char x)
{
	int i,g,h;
	g=(s[u-1]=='G')||(s[v-1]=='G'),h=(s[u-1]=='H')||(s[v-1]=='H');
	if(dep[v]>dep[u]) swap(u,v);
	for(i=20;i>=0;i--)
	{
		if(dep[fa[u][i]]>=dep[v])
		{
			h=h||hcow[u][i];
			g=g||gcow[u][i];
			u=fa[u][i];
		}
	}
	if(u==v)
	{
		if(x=='H') return h!=0;
		else return g!=0;
	}
	for(i=20;i>=0;i--)
	{
		if(fa[u][i]!=fa[v][i])
		{
			h=h||hcow[u][i]||hcow[v][i];
			g=g||gcow[u][i]||gcow[v][i];
			u=fa[u][i];
			v=fa[v][i];
		}
	}
	h=h||hcow[u][0]||gcow[v][0];
	g=g||gcow[u][0]||gcow[v][0];
	if(x=='H') return h!=0;
	else return g!=0;
}
signed main()
{
	int i,j,k,uu,vv;
	char xx;
	cin>>n;
	cin>>m;
	cin>>s;
	add_edge(0,1);
	for(i=1;i<n;i++)
	{
		cin>>uu>>vv;
		add_edge(uu,vv);
		add_edge(vv,uu);
	}
	DFS_init(1);
	for(i=1;i<=m;i++)
	{
		cin>>uu>>vv>>xx;
		cout<<get_LCA(uu,vv,xx);
	}
}