| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1153340 | son2008 | Lampice (COCI19_lampice) | C11 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
using namespace std;
#define task "task"
#define ii pair<int,int>
#define fi first
#define se second
#define int long long
#define ll long long
#define ld double
#define mp make_pair
#define lg2 20
#define iii pair<int,ii>
#define iiii pair<ii,ii>
#define fii fi.fi
#define fis fi.se3
#define sfi se.fi
#define see se.se
#define base 31
int dx[]={0LL,0LL,1,-1,1,1,-1,-1};
int dy[]={1,-1,0LL,0LL,1,-1,1,-1};
const int maxn=5e4+5;
const int mod=1e9+7;
int n,root,sz[maxn],h[maxn],q,par[maxn],ans=2e9,mn[maxn],mx_h,k,s[maxn],pw[maxn],H;
bool is_centroid[maxn];
vector<int>a[maxn];
void dfs(int u,int cha)
{
sz[u]=1;
for(int v:a[u])
{
if(v==cha||is_centroid[v])continue;
dfs(v,u);
sz[u]+=sz[v];
}
}
int find_centroid(int u,int tree_sz,int cha)
{
for(int v:a[u])
if(v!=cha&&!is_centroid[v]&&sz[v]>tree_sz/2) return find_centroid(v,tree_sz,u);
return u;
}
map<int,bool>d[maxn];
bool get(int u,int cha,int h,int down,int up)
{
mx_h=max(mx_h,h);
if(h>H)return false;
down=(down*base+s[u])%mod;
up=(s[u]*pw[h-1]+up)%mod;
int x=(up*pw[H-h]-down+mod)%mod;
// cout<<0<<" "<<down<<" "<<up<<" "<<h<<" "<<x<<" "<<d[h][x]<<'\n';
if(d[H-h][x])return true;
if(up==down&&h==H)return true;
for(int v:a[u])
{
if(v==cha||is_centroid[v])continue;
if(get(v,u,h+1,down,up))return true;
}
return false;
}
void update(int u,int cha,int h,int down,int up)
{
mx_h=max(mx_h,h);
if(h>H)return;
down=(down*base+s[u])%mod;
up=(s[u]*pw[h-1]+up)%mod;
int x=(up*pw[H-h]-down+mod)%mod;
d[h][x]=true;
//cout<<1<<" "<<down<<" "<<up<<" "<<h<<" "<<x<<'\n';
for(int v:a[u])
{
if(v==cha||is_centroid[v])continue;
update(v,u,h+1,down,up);
}
}
bool build_centroid(int u,int pre_centroid)
{
dfs(u,-1);
int centroid=find_centroid(u,sz[u],-1);
if(root==0)root=centroid;
mx_h=0;
is_centroid[centroid]=true;
for(int v:a[centroid])
{
if(!is_centroid[v])
{
if(get(v,centroid,2,s[centroid],s[centroid]))return true;
update(v,centroid,1,0,0);
}
}
for(int i=0;i<=mx_h;i++)d[i].clear();
for(int v:a[centroid])
{
if(!is_centroid[v])if(build_centroid(v,centroid))return true;
}
return false;
}
bool check(int mid)
{
for(int i=1;i<=n;i++)d[i].clear(),is_centroid[i]=false;
H=mid;
return build_centroid(1,-1);
}
void init()
{
string c;
cin>>n>>c;
for(int i=0;i<n;i++)
{
s[i+1]=c[i]-'a'+1;
}
for(int i=1;i<n;i++)
{
int u,v;
cin>>u>>v;
a[u].push_back(v);
a[v].push_back(u);
}
pw[0]=1;
for(int i=1;i<=n;i++) pw[i]=(pw[i-1]*base)%mod;
}
void process()
{
int ans=1;
int l=1,r=n;
while(l<=r)
{
int mid=(l+r)/2;
if(check(2*mid))
{
ans=max(ans,2*mid);
l=mid+1;
}
else r=mid-1;
}
l=1,r=n;
while(l<=r)
{
int mid=(l+r)/2;
if(check(2*mid+1))
{
ans=max(ans,2*mid+1);
l=mid+1;
}
else r=mid-1;
}
cout<<ans;
}
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
if(fopen(task".inp","r"))
{
freopen(task".inp","r",stdin);
freopen(task".out","w",stdout);
}
init();
process();
cerr <<endl<< "TIME : " << clock() * 0.001 << "s" << endl ;
}