用LCT维护树哈希，然后判断，之后每次跳树上 k 级祖先查找。

已经不知道怎么卡了，保证做法正确复杂度正确。

#pragma comment(linker,"/stack:200000000")
#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define fastcall __attribute__((optimize("-O3")))
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cctype>
#include<ctime>
#define N 614514
using namespace std;
int n,m;
int head[N],to[N],nxt[N],tot;
int fi[N];
char val[N],s[N];
inline int read(){
    int s=0,w=0;
    char ch=getchar();
    for(;!isdigit(ch);ch=getchar());
    for(;isdigit(ch);ch=getchar())s=(s<<1)+(s<<3)+(ch^48);
    return w?-s:s;
}
void add(int u,int v){
	to[++tot]=v;
	nxt[tot]=head[u];
	head[u]=tot;
}
int son[N],top[N],id[N],idx,dep[N],siz[N],f[N];
int cid[N];
void dfs1(int x,int fa){
	dep[x]=dep[fa]+1;f[x]=fa;
	siz[x]=1;
	int mx=-1;
	for(int i=head[x];i;i=nxt[i]){
		int y=to[i];
		if(y==fa)continue;
		dfs1(y,x);
		siz[x]+=siz[y];
		if(mx<siz[y])mx=siz[y],son[x]=y;
	}
}
void dfs2(int x,int topx){
	top[x]=topx;id[x]=++idx;s[idx]=val[x];
	cid[idx]=x;
	if(!son[x])return;
	dfs2(son[x],topx);
	for(int i=head[x];i;i=nxt[i]){
		int y=to[i];
		if(y==f[x]||y==son[x])continue;
		dfs2(y,y);
	}
}
int base,p=100000267;
void csh(){fi[0]=1;for(int i=1;i<N;i++)fi[i]=(fi[i-1]*base)%p;}
int lca(int x,int y){
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		x=f[top[x]];
	}
	if(dep[x]>dep[y])swap(x,y);
	return x;
}
struct link_cut_tree{
	int ch[N][2],f[N],st[N],hash[N],cnt[N];
	char val[N];
	bool r[N];
	#define lc ch[x][0]
	#define rc ch[x][1]
	void pushup(int x){
		cnt[x]=cnt[lc]+cnt[rc]+1;
		hash[x]=((hash[lc]*fi[cnt[rc]+1])%p+(val[x]-'a')*fi[cnt[rc]]%p+hash[rc])%p;
	}
	void rev(int x){swap(lc,rc),r[x]^=1;}
	int nroot(int x){return ch[f[x]][1]==x||ch[f[x]][0]==x;}
	int son(int x){return ch[f[x]][1]==x;}
	void rotate(int x){
		int y=f[x],z=f[y],k=son(x),w=ch[x][!k];
		if(nroot(y))ch[z][son(y)]=x;
		ch[x][!k]=y,ch[y][k]=w;
		if(w)f[w]=y;
		f[x]=z,f[y]=x;
		pushup(y);
	}
	void pushdown(int x){
		if(r[x]){
			if(lc)rev(lc);
			if(rc)rev(rc);
			r[x]=0;
		}
	}
	void splay(int x){
		int y=x,z=0;
		st[++z]=y;
		while(nroot(y))st[++z]=y=f[y];
		while(z)pushdown(st[z--]);
		while(nroot(x)){
			y=f[x];
			if(nroot(y))rotate(son(x)!=son(y)?x:y);
			rotate(x);
		}
		pushup(x);
	}
	void access(int x){for(int y=0;x;x=f[y=x])splay(x),rc=y,pushup(x);}
	void makeroot(int x){access(x),splay(x),rev(x);}
	void split(int x,int y){makeroot(x),access(y),splay(y);}
	void link(int x,int y){makeroot(x),f[x]=y;}
}lct;
int query(int x,int y){
	lct.split(x,y);
	return lct.hash[y];
}
int quk(int x,int k,int rt){
	while(k>=id[x]-id[top[x]]+1&&x!=rt){
		k-=id[x]-id[top[x]]+1;
		x=f[top[x]];
	}
	return cid[id[x]-k];
}
int queryk(int x,int y,int k){
	int c=lca(x,y),d=dep[x]+dep[y]-2*dep[c]+1;
	if(k==1)return x;
	k--;
	if(k<dep[x]-dep[c]+1)return quk(x,k,c);
	else return quk(y,d-k-1,c);
}
int lcp(int a,int b,int c,int d){
	int lc1=lca(a,b),r1=dep[a]+dep[b]-2*dep[lc1]+1;
	int lc2=lca(c,d),r2=dep[c]+dep[d]-2*dep[lc2]+1;
	int l=1,r=min(r1,r2);
	while(l<=r){
		int mid=(l+r)>>1;
		int ar=queryk(a,b,mid),br=queryk(c,d,mid);
		if(query(a,ar)==query(c,br))l=mid+1;
		else r=mid-1;
	}
	return r;
}
signed main(){
	//freopen("CF504Eyl.in","r",stdin);
	//freopen("cgetansCF504E.out","w",stdout);
	srand(time(0));
	base=rand()%200*10+rand()%2000;
	scanf("%d",&n);
	scanf("%s",val+1);
	csh();
	for(int i=1;i<=n;i++)lct.val[i]=val[i],lct.cnt[i]=1;
	for(int i=1;i<n;i++){
		int a,b;
		a=read(),b=read();
		lct.link(a,b);
		add(a,b);add(b,a);
	}
	dfs1(1,0);dfs2(1,1);
	scanf("%d",&m);
	while(m--){
		int a=read(),b=read(),c=read(),d=read();
		printf("%d\n",lcp(a,b,c,d));
	}
	return 0;
}