P5836 84分求助Wa on#6#11

#include<bits/stdc++.h>
using namespace std;
const int N=100010,M=N*2;
int head[N],ver[M],Next[M],edge[M],tot=0;
int f[N][22],t,d[N],dist[N],flag[N];
int n,m;
char s[N];
void add(int x,int y,int z){
	ver[++tot]=y,Next[tot]=head[x],head[x]=tot,edge[tot]=z;
}
void bfs(int root){
	d[root]=1;
	dist[root]=0;
	if(s[root]=='H')
		dist[root]=1;
	queue<int> q;
	q.push(root);
	while(q.size()){
		int x=q.front();
		q.pop();
		for(int i=head[x];i;i=Next[i]){
			int y=ver[i],z=edge[i];
			if(d[y])
				continue;
			d[y]=d[x]+1;
			dist[y]=dist[x]+z;
			q.push(y);
			f[y][0]=x; 
			for(int j=1;j<=t;j++)
				f[y][j]=f[f[y][j-1]][j-1];
		}
	}
}
int lca(int x,int y){
	if(d[x]<d[y])
		swap(x,y);
	for(int i=t;i>=0;i--)
		if(d[f[x][i]]>=d[y])
			x=f[x][i];
	if(x==y)
		return y;
	for(int i=t;i>=0;i--)
		if(f[x][i]!=f[y][i])
			x=f[x][i],y=f[y][i];
	return f[x][0];
}
int main(){
	scanf("%d %d",&n,&m);
	t=(int)log2(n)+1;
	scanf("%s",s+1);
	for(int i=1;i<n;i++){
		int x,y,z=0;
		scanf("%d %d",&x,&y);
		if(s[y]=='H')
			z=1;
		add(x,y,z);
		add(y,x,z);
	}
	bfs(1);
	for(int i=1;i<=m;i++){
		int x,y;
		char c;
		flag[i]=0;
		scanf("%d %d %c",&x,&y,&c);
		if(x==y){
			if(c==s[x])
				flag[i]=1;
			continue;
		}
		int Lca=lca(x,y);
		int distt=dist[x]+dist[y]-2*dist[Lca]+(s[Lca]=='H'),dd=d[x]+d[y]-2*d[Lca];
		if(distt>0&&c=='H')
			flag[i]=1;
		else if(distt<=dd&&c=='G')
			flag[i]=1;
	}
	for(int i=1;i<=m;i++)
		printf("%d",flag[i]);
	return 0;
}