待学习(树链剖分...\先学线段树和dfs序,好菜,呜呜呜)
贴下不完整的代码:

#include <bits/stdc++.h>
using namespace std;
const int N=3e5+50,M=20;
const int base=131;
typedef unsigned long long ull;
ull w[N];
ull h[N],b[N];//h[i]假设根节点是1,统计1到i的hash值 b[i]表示(131^i)
int fa[N][M];
int dep[N];
vector<int>v[N];

void dfs(int u,int fa)
{
    h[u]=h[fa]*base+w[u];
    for(int i=0;i<(int)v[u].size();i++)
    {
        int son=v[u][i];
        if(son==fa)    continue;
        dfs(son,u);
    }
}//处理h数组.

void init(int u,int f,int depth)
{
    fa[u][0]=f;dep[u]=depth;
    for(int i=1;(1<<i)<=depth;i++)
    {
        fa[u][i]=fa[fa[u][i-1]][i-1];
    }
    for(int i=0;i<v[u].size();i++)
    {
        int x=v[u][i];
        if(f==x) continue;
        init(x,u,depth+1);
    }
}

int lca(int u1,int u2)
{
    if(dep[u2]>dep[u1]) swap(u1,u2);
    for(int i=19;i>=0;i--)
    {
        if(dep[fa[u1][i]]>=dep[u2]) u1=fa[u1][i];
    }
    if(u1==u2) return u1;
    for(int i=19;i>=0;i--)
    {
        if(fa[u1][i]!=fa[u2][i])
        {
            u1=fa[u1][i];
            u2=fa[u2][i];
        }
    }
    return fa[u1][0];
}

int main()
{
    int n,m;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        char c;cin>>c;
        w[i]=(c-'a'+1);
    }
    b[0]=1;
    for(int i=1;i<=n;i++)
    {
        b[i]=b[i-1]*base;
    }
    for(int i=1;i<n;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        v[x].push_back(y);
        v[y].push_back(x);
    }dfs(1,0);
    init();
    scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
        int    A,B,C,D;
        scanf("%d%d%d%d",&A,&B,&C,&D);
        int u1=lca(A,B);
        int u2=lca(C,D);

    }
    return 0;
}