AC题解

#include <bits/stdc++.h>
#define N 100005 
using namespace std;
int n,m,t,tot=0,head[N],ver[2*N],edge[2*N],Next[2*N],f[N][22],d[N],dist[N],lg[100005];
char s[100005];
int h[500005],g[500005];//h[i]表示树根到i共有多少H g[i]同理 
void add(int x,int y,int z)
{
    ver[++tot]=y,edge[tot]=z,Next[tot]=head[x],head[x]=tot;
}
void prework()
{
    queue<int>q;
    q.push(1);
    d[1]=1;
    if(s[0]=='H')
    {
        h[1]=1;
    }
    else g[1]=1;
    while(q.size())
    {
        int x=q.front();
        q.pop();
        int i;
        for(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;
            f[y][0]=x;//y节点的2^0倍祖先是x
            if(s[y-1]=='H')
            {
                h[y]=h[x]+1;
                g[y]=g[x];//别漏下！！！ 
            }
            else
            {
                g[y]=g[x]+1;
                h[y]=h[x];
            }
            int j;
            for(j=1;j<=lg[d[x]];j++)
            {
                f[y][j]=f[f[y][j-1]][j-1];
            }
            q.push(y);
            
        }
    }
}
int lca(int x,int y)
{
    if(d[x]<d[y])swap(x,y);//使得x深度较小 
    int i;
    while(d[x] > d[y])
    {
        x = f[x][lg[d[x]-d[y]] - 1];
    }
    if(x==y)return x;
    for(i=lg[d[x]] - 1;i>=0;i--)
    {
        if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];
    }
    return f[x][0];
}
int main()
{
    cin>>n>>m;
    int i;
    memset(d,0,sizeof(d));
    scanf("%s",s);
    for(i=1;i<=n-1;i++)
    {
        int x,y;
        cin>>x>>y;
        add(x,y,1);
        add(y,x,1);
    }
     for(int i = 1; i <= n+1; ++i)
        lg[i] = lg[i-1] + (1 << lg[i-1] == i);
    prework();
    vector<int>v; 
    for(i=1;i<=m;i++)
    {
        int a,b;
        char c;//
        scanf("%d%d",&a,&b);
         scanf(" %c",&c);///!!!!!!一定要这么写 
        int LCA=lca(a,b);
        if(c=='H')
        {
            if((h[a]+h[b]-2*h[LCA]+(s[LCA-1]=='H'?1:0))>0)v.push_back(1);
            else v.push_back(0);
        }
        else
        {
            if((g[a]+g[b]-2*g[LCA]+(s[LCA-1]=='G'?1:0))>0)v.push_back(1);
            else v.push_back(0);
        }
    }
    for(i=0;i<v.size();i++)cout<<v[i];
    return 0;
}