不懂。求调。

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int N = 3e5+5;

int n;
vector<int> g[N];
int son[N],fa[N],dep[N],siz[N],top[N];
int dfn[N],tot,rnk[N];

void dfs0(int u,int p,int d){
	fa[u]=p;
	siz[u]=1;
	dep[u]=d;
	for (auto v : g[u]){
		if (v^p){
			dfs0(v,u,d+1);
			siz[u]+=siz[v];
			if (siz[v]>siz[son[u]]){
				son[u]=v;
			}
		}
	}
}

void dfs1(int u,int tp){
	top[u]=tp;
	dfn[u]=++tot;
	rnk[dfn[u]]=u;
	if (!son[u]){
		return;
	}
	dfs1(son[u],tp);
	for (auto v : g[u]){
		if (v!=fa[u] && v!=son[u]){
			dfs1(v,v);
		}
	}
}

void pth(int u,int v,vector<pair<int,int> > &p){
	stack<pair<int,int> > st;
	while (top[u]!=top[v]){
		if (dep[top[u]]>dep[top[v]]){
			p.push_back({n+n+1-dfn[u],n+n+1-dfn[u]+dep[u]-dep[top[u]]});
			u=fa[top[u]];
		}
		else{
			st.push({dfn[v]-dep[v]+dep[top[v]],dfn[v]});
			v=fa[top[v]];
		}
	}
	if (dep[u]>dep[v]){
		p.push_back({n+n+1-dfn[u],n+n+1-dfn[v]});
	}
	else{
		p.push_back({dfn[u],dfn[v]});
	}
	while (!st.empty()){
		p.push_back(st.top()),st.pop();
	}
}

const ll mod = 998244353;

string s,x;
ll pw[N<<1],hsh[N<<1];

mt19937_64 rnd(time(0));

ll _hash(int l,int r){
	ll ans=hsh[r]-hsh[l-1]*pw[r-l+1]%mod;
	if (ans<0){
		ans+=mod;
	}
	return ans;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin>>n>>s;
	s=" "+s;
	x=" "; 
	for (int i=1; i<n; i++){
		int u,v;
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	pw[0]=1;
	dfs0(1,0,0),dfs1(1,1);
	for (int i=1; i<=2*n; i++){
		if (i<=n){
			x.push_back(s[rnk[i]]);
		}
		else{
			x.push_back(x[n+n+1-i]);
		}
	}
	ll bs=rnd()%1000000;
	for (int i=1; i<=2*n; i++){
		pw[i]=pw[i-1]*bs%mod;
		hsh[i]=(hsh[i-1]*bs+x[i]-'a')%mod;
	}
	int q;
	cin>>q;
	while (q--){
		int a,b,c,d;
		cin>>a>>b>>c>>d;
		if (s[a]!=s[c]){
			cout<<0<<"\n";
			continue;
		}
		vector<pair<int,int> > v1,v2;
		pth(a,b,v1),pth(c,d,v2);
		int i=0,j=0,ans=0;
		while (i<v1.size() && j<v2.size()){
			int l1=v1[i].first,r1=v1[i].second;
			int l2=v2[j].first,r2=v2[j].second;
			int mn=min(r1-l1+1,r2-l2+1);
			if (_hash(l1,l1+mn-1)!=_hash(l2,l2+mn-1)){
				int l=0,r=mn;
				while (l+1<r){
					int mid=l+r>>1;
					if (_hash(l1,l1+mid-1)!=_hash(l2,l2+mid-1)){
						r=mid;
					}
					else{
						l=mid;
					}
				}
				ans+=l;
				break;
			}
			ans+=mn,l1+=mn,l2+=mn;
			if (l1>r1){
				i++;
			}
			if (l2>r2){
				j++;
			}
		}
		cout<<ans<<"\n";
	}
	return 0;
}