#include<bits/stdc++.h>
using namespace std;
#define int long long
#define X first
#define Y second
int qpow(int x,int t,int md){
if(t==0){return 1;}
if(t%2==1){return x*qpow(x,t-1,md)%md;}
int xx=qpow(x,t/2,md);
return xx*xx%md;
}
int n;
string s;
vector<int>e[150005];
int __id;
void adde(int a,int b){
__id++;
e[a].push_back(__id);
e[__id].push_back(a);
e[b].push_back(__id);
e[__id].push_back(b);
}
int mi;
int mod[2]={998244353,1000000007};
int tme[1000006][2];int inv[1000006][2];
int okk;
int hsh[150005][2];
int rhsh[150005][2];
int dph[150005];
int sbsz[150005];
int vis[150005];
void dfssbsz(int nw,int pa,int &ctr,int fsz){
sbsz[nw]=1;
for(int i=0;i<e[nw].size();i++){
int v=e[nw][i];
if(v==pa||vis[v]){continue;}
dfssbsz(v,nw,ctr,fsz);
sbsz[nw]+=sbsz[v];
}
if(ctr==0&&sbsz[nw]*2>=fsz){
ctr=nw;
}
}
map<int,int>mp[200005];
int rrt;int mxdph;
void dfs(int nw,int pa,int typ){
dph[nw]=dph[pa]+1;
mxdph=max(mxdph,dph[nw]);
hsh[nw][0]=(hsh[pa][0]+(s[nw]-'a')*tme[dph[nw]][0])%mod[0];
rhsh[nw][0]=((s[nw]-'a')*tme[1][0]+rhsh[pa][0]*tme[1][0])%mod[0];
if(typ==1){
int c=hsh[nw][0];
int d=rhsh[nw][0];
int fv=(c*tme[mi*2+1-dph[nw]][0]-d+mod[0])%mod[0];
mp[dph[nw]][fv]=1;
}else{
if(dph[nw]<=mi*2+1){
int rv=(rhsh[nw][0]-(s[rrt]-'a')*tme[dph[nw]][0]%mod[0]+mod[0])%mod[0];
int v=(hsh[nw][0]-(s[rrt]-'a')*tme[1][0]%mod[0]+mod[0])*inv[1][0]%mod[0];
int fv=(v*tme[mi*2+1-(dph[nw]-1)][0]-rv+mod[0])%mod[0];
if(mp[mi*2+1-(dph[nw]-1)].find(fv)!=mp[mi*2+1-(dph[nw]-1)].end()){
okk=1;
}
}
}
for(int i=0;i<e[nw].size();i++){
int v=e[nw][i];
if(v==pa||vis[v]){continue;}
dfs(v,nw,typ);
}
}
void decompose(int rt){
int ctr=0;
dfssbsz(rt,0,ctr,n);
ctr=0;
dfssbsz(rt,0,ctr,sbsz[rt]);
rrt=ctr;
//cout<<sbsz[rt]<<" "<<ctr<<endl;
hsh[ctr][0]=(s[ctr]-'a')*tme[1][0]%mod[0];
rhsh[ctr][0]=(s[ctr]-'a')*tme[1][0]%mod[0];
mxdph=0;
dph[ctr]=1;
int c=hsh[ctr][0];
int d=rhsh[ctr][0];
int fv=(c*tme[mi*2+1-dph[ctr]][0]-d+mod[0])%mod[0];
mp[1][fv]=1;
for(int i=0;i<e[ctr].size();i++){
int v=e[ctr][i];
if(vis[v]){continue;}
dfs(v,ctr,2);
dfs(v,ctr,1);
}
/*
for(int i=1;i<=__id;i++){
cout<<hsh[i][0]<<" ";
}cout<<endl;
for(int i=1;i<=__id;i++){
cout<<rhsh[i][0]<<" ";
}cout<<endl;
*/
for(int i=0;i<=mxdph;i++){
mp[i].clear();
}
//if(okk){return;}
vis[ctr]=1;
for(int i=0;i<e[ctr].size();i++){
int v=e[ctr][i];
if(vis[v]){continue;}
decompose(v);
}
}
int chk(int v){
mi=v;
for(int i=0;i<=__id;i++){
vis[i]=0;
}
okk=0;
decompose(1);
return okk;
}
void precalc(){
tme[0][0]=1;
tme[0][1]=1;
for(int i=1;i<=200000;i++){
tme[i][0]=tme[i-1][0]*37%mod[0];
tme[i][1]=tme[i-1][1]*37%mod[1];
inv[i][0]=qpow(tme[i][0],mod[0]-2,mod[0]);
inv[i][1]=qpow(tme[i][1],mod[1]-2,mod[1]);
}
}
//1073
signed main(){
//cout<<'~'-'a'<<endl;
precalc();
cin>>n>>s;
s="*"+s;
for(int i=1;i<=n*3;i++){
s+="~";
}
__id=n;
for(int i=1;i<=n-1;i++){
int a;int b;
cin>>a>>b;
adde(a,b);
}
for(int i=1;i<=n;i++){
if(e[i].size()==1){
e[i].push_back(++__id);
e[__id].push_back(i);
}
}
/*
for(int i=1;i<=__id;i++){
for(int j=0;j<e[i].size();j++){
cout<<e[i][j]<<" ";
}cout<<endl;
}
*/
int v;/*
while(cin>>v){
cout<<chk(v)<<endl;
}*/
int l=1;int r=n;
while(l<r){
int mi=l+(r-l+1)/2;
if(chk(mi)){
l=mi;
}else{
r=mi-1;
}
}
cout<<l<<endl;
}
Compilation message
lampice.cpp: In function 'void dfssbsz(long long int, long long int, long long int&, long long int)':
lampice.cpp:34:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
34 | for(int i=0;i<e[nw].size();i++){
| ~^~~~~~~~~~~~~
lampice.cpp: In function 'void dfs(long long int, long long int, long long int)':
lampice.cpp:66:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
66 | for(int i=0;i<e[nw].size();i++){
| ~^~~~~~~~~~~~~
lampice.cpp: In function 'void decompose(long long int)':
lampice.cpp:88:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
88 | for(int i=0;i<e[ctr].size();i++){
| ~^~~~~~~~~~~~~~
lampice.cpp:108:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
108 | for(int i=0;i<e[ctr].size();i++){
| ~^~~~~~~~~~~~~~
lampice.cpp: In function 'int main()':
lampice.cpp:165:5: warning: unused variable 'v' [-Wunused-variable]
165 | int v;/*
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
210 ms |
19600 KB |
Output is correct |
| 2 |
Correct |
218 ms |
19656 KB |
Output is correct |
| 3 |
Correct |
254 ms |
20040 KB |
Output is correct |
| 4 |
Correct |
284 ms |
20132 KB |
Output is correct |
| 5 |
Correct |
202 ms |
19432 KB |
Output is correct |
| 6 |
Correct |
203 ms |
19492 KB |
Output is correct |
| 7 |
Correct |
205 ms |
19404 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2646 ms |
40004 KB |
Output is correct |
| 2 |
Correct |
2768 ms |
40344 KB |
Output is correct |
| 3 |
Correct |
3039 ms |
40900 KB |
Output is correct |
| 4 |
Correct |
3043 ms |
41984 KB |
Output is correct |
| 5 |
Correct |
3443 ms |
43060 KB |
Output is correct |
| 6 |
Correct |
2528 ms |
39996 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5074 ms |
37048 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
210 ms |
19600 KB |
Output is correct |
| 2 |
Correct |
218 ms |
19656 KB |
Output is correct |
| 3 |
Correct |
254 ms |
20040 KB |
Output is correct |
| 4 |
Correct |
284 ms |
20132 KB |
Output is correct |
| 5 |
Correct |
202 ms |
19432 KB |
Output is correct |
| 6 |
Correct |
203 ms |
19492 KB |
Output is correct |
| 7 |
Correct |
205 ms |
19404 KB |
Output is correct |
| 8 |
Correct |
2646 ms |
40004 KB |
Output is correct |
| 9 |
Correct |
2768 ms |
40344 KB |
Output is correct |
| 10 |
Correct |
3039 ms |
40900 KB |
Output is correct |
| 11 |
Correct |
3043 ms |
41984 KB |
Output is correct |
| 12 |
Correct |
3443 ms |
43060 KB |
Output is correct |
| 13 |
Correct |
2528 ms |
39996 KB |
Output is correct |
| 14 |
Execution timed out |
5074 ms |
37048 KB |
Time limit exceeded |
| 15 |
Halted |
0 ms |
0 KB |
- |
