CF504E 题解

#include<bits/stdc++.h>
#define REG register
#define MAXN 600005
#define LL long long
using namespace std;
inline void read(int& x){
    static char c=getchar();
    while(!isdigit(c=getchar()));x=c^48;
    while(isdigit(c=getchar()))x=(x*10)+(c^48);
}
inline int Pow(int a,int b,const int& Mod){
    int ans=1;
    while(b){
        if(b&1) ans=1ll*ans*a%Mod;
        a=1ll*a*a%Mod,b>>=1;
    }
    return ans;
}

int n,m;
char str[MAXN];

// Save Tree

struct Edge{
    int v,nxt;
}ed[MAXN<<1];
int head[MAXN],cnt;
inline void adde(int u,int v){ed[++cnt]=(Edge){v,head[u]},head[u]=cnt;}
inline void add(int u,int v){adde(u,v),adde(v,u);}
#define FORE(i,Now) for(REG int i=head[Now];i;i=ed[i].nxt)

// Get k-th Father & LCA

int Dep[MAXN],MDep[MAXN],Top[MAXN],Son[MAXN],HighBit[MAXN];
int Fat[30][MAXN];
vector<int> Up[MAXN],Down[MAXN];
int ST[30][MAXN<<1],Dfn[MAXN],Idx;

inline int Min(int x,int y){return Dep[x]<Dep[y]?x:y;}

void Dfs1(int Now){
    ST[0][Dfn[Now]=++Idx]=Now;
    MDep[Now]=Dep[Now]=Dep[Fat[0][Now]]+1;
    FORE(i,Now){
        int v=ed[i].v;
        if(v==Fat[0][Now]) continue;
        Fat[0][v]=Now;
        for(REG int j=0;Fat[j][v];++j)
            Fat[j+1][v]=Fat[j][Fat[j][v]];
        Dfs1(v);
        ST[0][++Idx]=Now;
        if(MDep[v]>MDep[Now]) MDep[Now]=MDep[v],Son[Now]=v;
    }
}

void Dfs2(int Now,int top){
    Top[Now]=top;
    if(top==Now){
        for(REG int i=0,f=Now;i<=MDep[Now]-Dep[Now];++i)
            Up[Now].push_back(f),f=Fat[0][f];
        for(REG int i=0,f=Now;i<=MDep[Now]-Dep[Now];++i)
            Down[Now].push_back(f),f=Son[f];
    }
    if(Son[Now]) Dfs2(Son[Now],top);
    FORE(i,Now){
        int v=ed[i].v;
        if(v==Fat[0][Now]||v==Son[Now]) continue;
        Dfs2(v,v);
    }
}

inline void TInit(){
    HighBit[1]=0;
    for(REG int i=2;i<=(n<<1);++i) HighBit[i]=HighBit[i>>1]+1;
    for(REG int j=1;j<=20;++j)
        for(REG int i=1;i<=(n<<1);++i)
            ST[j][i]=Min(ST[j-1][i],ST[j-1][i+(1<<(j-1))]);
}

inline int GetLCA(int x,int y){
    if(Dfn[x]>Dfn[y]) swap(x,y);
    x=Dfn[x],y=Dfn[y];
    int k=HighBit[y-x+1];
    return Min(ST[k][x],ST[k][y-(1<<k)+1]);
}

inline int GetkFa(int x,int k){
    if(k>=Dep[x]) return 0;
    if(!k) return x;
    x=Fat[HighBit[k]][x],k-=(1<<HighBit[k]);
    k-=Dep[x]-Dep[Top[x]],x=Top[x];
    return k>=0?Up[x][k]:Down[x][-k];
}

// Hash of String

namespace Hash{
    const int Mod1=998244353,Mod2=19260817;
    int Bas1,Bas2;
    int BsP1[MAXN],BsP2[MAXN];
    int BsIP1[MAXN],BsIP2[MAXN];
    inline void Init(){
        srand((unsigned)time(NULL));Bas1=rand()%100+100,Bas2=rand()%100+200;
        BsP1[0]=1,BsP1[1]=Bas1,BsIP1[1]=Pow(Bas1,Mod1-2,Mod1);
        BsP2[0]=1,BsP2[1]=Bas2,BsIP2[1]=Pow(Bas2,Mod2-2,Mod2);
        for(REG int i=2;i<=n;++i) BsP1[i]=1ll*BsP1[i-1]*Bas1%Mod1;
        for(REG int i=2;i<=n;++i) BsP2[i]=1ll*BsP2[i-1]*Bas2%Mod2;
        for(REG int i=2;i<=n;++i) BsIP1[i]=1ll*BsIP1[i-1]*BsIP1[1]%Mod1;
        for(REG int i=2;i<=n;++i) BsIP2[i]=1ll*BsIP2[i-1]*BsIP2[1]%Mod2;
    }
    struct HashData{int Hs1,Hs2,Len;};
    #define HD HashData
    inline HD PushBack(HD& S,char c){return (HD){(1ll*S.Hs1*Bas1+c)%Mod1,(1ll*S.Hs2*Bas2+c)%Mod2,S.Len+1};}
    inline HD PushFront(HD& S,char c){return (HD){(1ll*c*BsP1[S.Len]+S.Hs1)%Mod1,(1ll*c*BsP2[S.Len]+S.Hs2)%Mod2,S.Len+1};}
    inline HD operator+(const HD& a,const HD& b){return (HD){(1ll*a.Hs1*BsP1[b.Len]+b.Hs1)%Mod1,(1ll*a.Hs2*BsP2[b.Len]+b.Hs2)%Mod2,a.Len+b.Len};}
    inline bool operator==(const HD& a,const HD& b){return a.Hs1==b.Hs1&&a.Hs2==b.Hs2&&a.Len==b.Len;}
    inline HD DelBack(const HD& a,const HD& b){return (HD){1ll*(a.Hs1-b.Hs1+Mod1)*BsIP1[b.Len]%Mod1,1ll*(a.Hs2-b.Hs2+Mod2)*BsIP2[b.Len]%Mod2,a.Len-b.Len};}
    inline HD DelFront(const HD& a,const HD& b){return (HD){(a.Hs1-1ll*b.Hs1*BsP1[a.Len-b.Len]%Mod1+Mod1)%Mod1,(a.Hs2-1ll*b.Hs2*BsP2[a.Len-b.Len]%Mod2+Mod2)%Mod2,a.Len-b.Len};}
}

Hash::HD RTL[MAXN],LTR[MAXN];

void GetHashDfs(int Now,int Fa){
    if(Now==1) RTL[Now]=LTR[Now]=(Hash::HD){str[Now],str[Now],1};
    else RTL[Now]=Hash::PushBack(RTL[Fa],str[Now]),LTR[Now]=Hash::PushFront(LTR[Fa],str[Now]);
    FORE(i,Now){
        int v=ed[i].v;
        if(v==Fa) continue;
        GetHashDfs(v,Now);
    }
}

inline void GetHash(){Hash::Init();LTR[0]=RTL[0]=(Hash::HD){0,0,0};GetHashDfs(1,0);}

inline Hash::HD GetStr(int a,int b,int lca,int len,int k){
    if(Dep[a]-k+1>Dep[lca]) return DelBack(LTR[a],LTR[GetkFa(a,k)]);
    else return DelBack(LTR[a],LTR[lca])+DelFront(RTL[GetkFa(b,len-k)],RTL[Fat[0][lca]]);
}

inline int Query(int a,int b,int c,int d){
    int LCAA=GetLCA(a,b),LCAB=GetLCA(c,d);
    int LenA=Dep[a]+Dep[b]-2*Dep[LCAA]+1,LenB=Dep[c]+Dep[d]-2*Dep[LCAB]+1;
    int l=1,r=min(LenA,LenB),mid,ans=0;
    while(l<=r){
        mid=(l+r)>>1;
        if(GetStr(a,b,LCAA,LenA,mid)==GetStr(c,d,LCAB,LenB,mid)) ans=mid,l=mid+1;
        else r=mid-1;
    }
    return ans;
}

inline void Work(){
    scanf("%d\n",&n);
    scanf("%s",str+1);
    for(REG int i=1;i<n;++i){
        int u,v;
        read(u),read(v);
        add(u,v);
    }
    GetHash(),Dfs1(1),Dfs2(1,1),TInit();
    read(m);
    while(m--){
        int a,b,c,d;
        read(a),read(b),read(c),read(d);
        printf("%d\n",Query(a,b,c,d));
    }
}

int main(){Work();}