#include<bits/stdc++.h>
using namespace std;
#define int long long
#define FOR(a,b,c) for(int a=b, __c=c; a<=__c; ++a)
#define FORD(a,b,c) for(int a=b, __c=c; a>=__c; --a)
#define forv(a,b) for(auto &a:b)
#define ii pair<int,int>
#define fi first
#define se second
#define all(a) begin(a),end(a)
#define reset(f,x) memset(f,x,sizeof(f))
#define pb push_back
#define eb emplace_back
#define fasty ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define gg exit(0);
#define bit(x,i) (x>>(i-1)&1ll)
#define on(x,i) (x|(1ll<<(i-1)))
#define off(x,i) (x&~(1ll<<(i-1)))
using ull=unsigned long long;
const int N=5e4+5;
const int base=19937;
int n;
char a[N];
vector<int> ad[N];
ull pw[N];
int dd[N],sz[N],cnt;
int dep[N];
ull hash_up[N], hash_down[N];
int pd[N][32];
vector<pair<ull,int>> has[N];
vector<int> node;
bool ok=false;
void dfs(int u,int par){
sz[u]=1; cnt++;
forv(v,ad[u]) if(!dd[v] && v!=par) dfs(v,u), sz[u]+=sz[v];
}
int ftr(int u,int par){
forv(v,ad[u]) if(!dd[v] && v!=par && sz[v]>cnt/2) return ftr(v,u);
return u;
}
void prep(int u,int par){
node.pb(u);
FOR(i,1,20) pd[u][i]=pd[pd[u][i-1]][i-1];
hash_up[u]=hash_up[par]+pw[dep[u]-1]*(a[u]-'a'+1);
hash_down[u]=hash_down[par]*base+(a[u]-'a'+1);
has[dep[u]].pb(make_pair(hash_down[u],u));
forv(v,ad[u]) if(v!=par && !dd[v]){
pd[v][0]=u;
dep[v]=dep[u]+1;
prep(v,u);
}
}
int jump(int u,int dep){
FORD(i,20,0) if(dep>>i&1) u=pd[u][i];
return u;
}
int lca(int u,int v){
if(dep[u]<dep[v]) swap(u,v);
int _=dep[u]-dep[v];
u=jump(u,_);
if(u==v) return u;
FORD(i,20,0) if(pd[u][i]!=pd[v][i]) u=pd[u][i], v=pd[v][i];
return pd[u][0];
}
ull que(int u,int v){
return hash_down[u]-hash_down[pd[v][0]]*pw[dep[u]-dep[v]+1];
}
void solve(int u,int L){
if(ok) return;
node.clear();
dep[u]=1;
pd[u][0]=0;
hash_up[u]=hash_down[u]=0;
prep(u,u);
FOR(i,1,n) if(has[i].size()){
sort(all(has[i]));
} else break;
forv(v,node){
if(ok) break;
int len=L-dep[v]+1;
if(len>dep[v] || len<1) continue;
int x=jump(v,len-1);
if(hash_down[x]!=hash_up[x]) continue;
ull C=que(v,x);
auto p=lower_bound(all(has[len]), pair<ull,int>(C,-1))-begin(has[len]);
if(p==has[len].size() || has[len][p].fi!=C) continue;
while(p<has[len].size()){
if(has[len][p].fi != C) break;
int _=has[len][p].se;
if(lca(v,_)==u){
ok=1;
break;
}
else p++;
}
}
FOR(i,1,n) if(has[i].size()) has[i].clear(); else break;
}
void ctr(int u,int L){
if(ok) return;
cnt=0;
dfs(u,0);
int C=ftr(u,0);
dd[C]=1;
solve(C,L);
forv(v,ad[C]) if(!dd[v]) ctr(v,L);
}
bool chk(int len,int odd){
len=len*2+odd;
ok=false;
FOR(i,1,n) dd[i]=0;
ctr(1,len);
return ok;
}
int32_t main(){
fasty;
#define task "lampice"
if(fopen(task".in","r")) freopen(task".in","r",stdin);
cin>>n;
FOR(i,1,n) cin>>a[i];
FOR(i,1,n-1){
int u,v;
cin>>u>>v;
ad[u].pb(v); ad[v].pb(u);
}
pw[0]=1;
FOR(i,1,n) pw[i]=pw[i-1]*base;
int l=0, r=n/2, rett=0;
while(l<=r){
int m=l+(r-l)/2;
if(chk(m,1)) rett=m, l=m+1;
else r=m-1;
}
int ans=rett*2+1;
l=1, r=n/2, rett=0;
while(l<=r){
int m=l+(r-l)/2;
if(chk(m,0)) rett=m, l=m+1;
else r=m-1;
}
ans=max(ans,rett*2);
cout<<ans<<'\n';
}
Compilation message
lampice.cpp: In function 'void solve(long long int, long long int)':
lampice.cpp:94:11: warning: comparison of integer expressions of different signedness: 'long int' and 'std::vector<std::pair<long long unsigned int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
94 | if(p==has[len].size() || has[len][p].fi!=C) continue;
| ~^~~~~~~~~~~~~~~~~
lampice.cpp:95:14: warning: comparison of integer expressions of different signedness: 'long int' and 'std::vector<std::pair<long long unsigned int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
95 | while(p<has[len].size()){
| ~^~~~~~~~~~~~~~~~
lampice.cpp: In function 'int32_t main()':
lampice.cpp:129:36: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
129 | if(fopen(task".in","r")) freopen(task".in","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
2816 KB |
Output is correct |
| 2 |
Correct |
12 ms |
3072 KB |
Output is correct |
| 3 |
Correct |
36 ms |
3328 KB |
Output is correct |
| 4 |
Correct |
51 ms |
3584 KB |
Output is correct |
| 5 |
Correct |
3 ms |
2688 KB |
Output is correct |
| 6 |
Correct |
4 ms |
2688 KB |
Output is correct |
| 7 |
Correct |
3 ms |
2688 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2380 ms |
20972 KB |
Output is correct |
| 2 |
Correct |
1782 ms |
21488 KB |
Output is correct |
| 3 |
Correct |
1205 ms |
21872 KB |
Output is correct |
| 4 |
Correct |
1406 ms |
22768 KB |
Output is correct |
| 5 |
Correct |
2347 ms |
23664 KB |
Output is correct |
| 6 |
Correct |
435 ms |
23668 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5030 ms |
22128 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
2816 KB |
Output is correct |
| 2 |
Correct |
12 ms |
3072 KB |
Output is correct |
| 3 |
Correct |
36 ms |
3328 KB |
Output is correct |
| 4 |
Correct |
51 ms |
3584 KB |
Output is correct |
| 5 |
Correct |
3 ms |
2688 KB |
Output is correct |
| 6 |
Correct |
4 ms |
2688 KB |
Output is correct |
| 7 |
Correct |
3 ms |
2688 KB |
Output is correct |
| 8 |
Correct |
2380 ms |
20972 KB |
Output is correct |
| 9 |
Correct |
1782 ms |
21488 KB |
Output is correct |
| 10 |
Correct |
1205 ms |
21872 KB |
Output is correct |
| 11 |
Correct |
1406 ms |
22768 KB |
Output is correct |
| 12 |
Correct |
2347 ms |
23664 KB |
Output is correct |
| 13 |
Correct |
435 ms |
23668 KB |
Output is correct |
| 14 |
Execution timed out |
5030 ms |
22128 KB |
Time limit exceeded |
| 15 |
Halted |
0 ms |
0 KB |
- |
