1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
| #include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pi;
typedef long long ll;
inline int gin() {
int s=0,f=1;
char c=getchar();
while(c<'0' || c>'9') {
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9') {
s=(s<<3)+(s<<1)+(c^48);
c=getchar();
}
return s*f;
}
const int N=3e5+5,mod=1e9+7;
int n,m,dep[N],sz[N],son[N],fa[N],dfn[N],zmz[N],top[N],dfc;
char str[N];
const pi B={131,13331};
pi bin[N],h1[N],h2[N];
vector<int> e[N];
inline pi operator + (pi a,pi b) {return {(a.first+b.first)%mod,(a.second+b.second)%mod};}
inline pi operator - (pi a,pi b) {return {(a.first-b.first+mod)%mod,(a.second-b.second+mod)%mod};}
inline pi operator * (pi a,pi b) {return {1ll*a.first*b.first%mod,1ll*a.second*b.second%mod};}
inline pi Hash(bool op,int x,int k) {
if(op) return h2[x-k+1]-h2[x+1]*bin[k];
return h1[x+k-1]-h1[x-1]*bin[k];
}
void dfs1(int u,int f) {
sz[u]=1,dep[u]=dep[fa[u]=f]+1;
for(int v:e[u]) if(v!=f) {
dfs1(v,u);
sz[u]+=sz[v];
if(sz[v]>sz[son[u]]) son[u]=v;
}
}
void dfs2(int u,int topf) {
top[u]=topf,dfn[u]=++dfc,zmz[dfc]=u;
if(son[u]) dfs2(son[u],topf);
for(int v:e[u]) if(!top[v]) dfs2(v,v);
}
int lca(int x,int y) {
while(top[x]!=top[y]) {
if(dep[top[x]]<dep[top[y]]) swap(x,y);
x=fa[top[x]];
}
return dep[x]<dep[y]?x:y;
}
vector<pi> get(int x,int y) {
int z=lca(x,y);
vector<pi> q1,q2;
while(dep[top[x]]>dep[z]) q1.push_back({x,top[x]}),x=fa[top[x]];
q1.push_back({x,z});
while(dep[top[y]]>dep[z]) q2.push_back({top[y],y}),y=fa[top[y]];
if(y!=z) q2.push_back({son[z],y});
while(q2.size()) q1.push_back(q2.back()),q2.pop_back();
return q1;
}
signed main() {
#ifndef ONLINE_JUDGE
freopen("test.in","r",stdin);
freopen("test.out","w",stdout);
#endif
n=gin();
scanf("%s",str+1);
bin[0]={1,1},bin[1]=B;
for(int i=1;i<n;i++) {
int u=gin(),v=gin();
e[u].push_back(v),e[v].push_back(u);
bin[i+1]=bin[i]*B;
}
dfs1(1,0);
dfs2(1,1);
for(int i=1;i<=n;i++) {
h1[i]=h1[i-1]*B+(pi){str[zmz[i]],str[zmz[i]]};
h2[n-i+1]=h2[n-i+2]*B+(pi){str[zmz[n-i+1]],str[zmz[n-i+1]]};
}
m=gin();
while(m--) {
int a=gin(),b=gin(),c=gin(),d=gin(),ans=0,s=0,t=0;
vector<pi> f=get(a,b),g=get(c,d);
while(s<f.size() && t<g.size()) {
int fl=dfn[f[s].first],fr=dfn[f[s].second];
int gl=dfn[g[t].first],gr=dfn[g[t].second];
bool tf=fl>fr,tg=gl>gr;
int lenf=(tf?fl-fr:fr-fl)+1;
int leng=(tg?gl-gr:gr-gl)+1;
int len=min(lenf,leng);
pi hf=Hash(tf,fl,len);
pi hg=Hash(tg,gl,len);
if(hf==hg) {
if(len==lenf) s++;
else f[s].first=zmz[fl+(tf?-1:1)*len];
if(len==leng) t++;
else g[t].first=zmz[gl+(tg?-1:1)*len];
ans+=len;
}
else {
int l=1,r=len;
while(l<r) {
int mid=l+r>>1;
hf=Hash(tf,fl,mid);
hg=Hash(tg,gl,mid);
if(hf==hg) l=mid+1;
else r=mid;
}
ans+=l-1;
break;
}
}
printf("%d\n",ans);
}
return 0;
}
|