#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 15e4;
const ll P = 31;
const ll MOD = 998244353;
ll mypow(ll x, ll y, ll m)
{
if(y==0) return 1;
if(y%2) return mypow(x, y-1, m)*x%m;
ll t=mypow(x, y/2, m);
return t*t%m;
}
ll inv(ll x, ll m)
{
return mypow(x, m-2, m);
}
int N;
vector<int> adj[MAXN+10];
char S[MAXN+10];
int D;
bool flag=false;
int sz[MAXN+10], del[MAXN+10];
void getsz(int now, int bef)
{
sz[now]=1;
for(int nxt : adj[now])
{
if(nxt==bef) continue;
if(del[nxt]) continue;
getsz(nxt, now);
sz[now]+=sz[nxt];
}
}
int getcen(int now, int bef, int S)
{
for(int nxt : adj[now])
{
if(nxt==bef) continue;
if(del[nxt]) continue;
if(sz[nxt]>S/2) return getcen(nxt, now, S);
}
return now;
}
int par[MAXN+10];
ll ppow[MAXN+10], ippow[MAXN+10];
int dep[MAXN+10];
ll H[MAXN+10], IH[MAXN+10];
void dfs(int now, int bef, int d)
{
par[now]=bef;
dep[now]=d;
H[now]=(H[bef]+ppow[d]*(S[now]-'a'+1)%MOD)%MOD;
IH[now]=(IH[bef]+ippow[d]*(S[now]-'a'+1)%MOD)%MOD;
for(int nxt : adj[now])
{
if(nxt==bef) continue;
dfs(nxt, now, d+1);
}
}
ll geth(int u, int v)
{
ll ret=0;
if(dep[u]<dep[v])
{
ret=((H[v]-H[par[u]])%MOD+MOD)%MOD;
ret=ret*ippow[dep[u]]%MOD;
}
else
{
ret=((IH[u]-IH[par[v]])%MOD+MOD)%MOD;
ret=ret*ppow[dep[u]]%MOD;
}
return ret;
}
unordered_set<ll> M;
void dfs2(int now, int bef, int root)
{
M.insert(geth(root, now));
for(int nxt : adj[now])
{
if(nxt==bef) continue;
dfs2(nxt, now, root);
}
}
vector<int> ST;
void dfs3(int now, int bef)
{
ST.push_back(now);
if(2*dep[now]-D>=0)
{
if(geth(ST[0], ST[2*dep[now]-D])==geth(ST[2*dep[now]-D], ST[0]) && M.find(geth(ST[2*dep[now]-D+1], now))!=M.end())
{
//printf("%d / %d %d\n", now, D, dep[now]);
flag=true;
}
}
for(int nxt : adj[now])
{
if(nxt==bef) continue;
dfs3(nxt, now);
}
ST.pop_back();
}
void decomp(int now)
{
getsz(now, now);
now=getcen(now, now, sz[now]);
del[now]=true;
dfs(now, 0, 0);
//printf("CENTROID %d\n", now);
M.clear();
ST.push_back(now);
for(int i=0; i<adj[now].size(); i++)
{
int nxt=adj[now][i];
if(del[nxt]) continue;
dfs3(nxt, now);
dfs2(nxt, now, nxt);
}
M.clear();
ST.push_back(now);
for(int i=adj[now].size()-1; i>=0; i--)
{
int nxt=adj[now][i];
if(del[nxt]) continue;
dfs3(nxt, now);
dfs2(nxt, now, nxt);
}
ST.clear();
for(int nxt : adj[now])
{
if(del[nxt]) continue;
decomp(nxt);
}
}
bool solve(int x)
{
D=x;
flag=false;
for(int i=1; i<=N; i++) del[i]=0;
decomp(1);
return flag;
}
int main()
{
scanf("%d", &N);
ppow[0]=1; ippow[0]=1;
ppow[1]=P; ippow[1]=inv(P, MOD);
for(int i=2; i<=N; i++) ppow[i]=ppow[i-1]*P%MOD;
for(int i=2; i<=N; i++) ippow[i]=ippow[i-1]*ippow[1]%MOD;
scanf(" %s", S+1);
for(int i=1; i<N; i++)
{
int u, v, w=N+i;
scanf("%d%d", &u, &v);
adj[u].push_back(w);
adj[w].push_back(u);
adj[v].push_back(w);
adj[w].push_back(v);
//printf("%d %d\n", u, w);
//printf("%d %d\n", v, w);
}
int t=N+N-1;
for(int i=1; i<=N; i++)
{
if(adj[i].size()==1)
{
int u=++t, v=i;
adj[u].push_back(v);
adj[v].push_back(u);
//printf("%d %d\n", u, v);
}
}
for(int i=N+1; i<=t; i++) S[i]='z'+1;
N=t;
int lo=1, hi=N;
while(lo+1<hi)
{
int mid=lo+hi>>1;
if(solve(mid*2)) lo=mid;
else hi=mid;
}
printf("%d\n", lo);
}
Compilation message
lampice.cpp: In function 'void decomp(int)':
lampice.cpp:136:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
136 | for(int i=0; i<adj[now].size(); i++)
| ~^~~~~~~~~~~~~~~~
lampice.cpp: In function 'int main()':
lampice.cpp:209:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
209 | int mid=lo+hi>>1;
| ~~^~~
lampice.cpp:173:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
173 | scanf("%d", &N);
| ~~~~~^~~~~~~~~~
lampice.cpp:180:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
180 | scanf(" %s", S+1);
| ~~~~~^~~~~~~~~~~~
lampice.cpp:184:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
184 | scanf("%d%d", &u, &v);
| ~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
606 ms |
4076 KB |
Output is correct |
| 2 |
Runtime error |
1914 ms |
8172 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5047 ms |
21652 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5051 ms |
18320 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
606 ms |
4076 KB |
Output is correct |
| 2 |
Runtime error |
1914 ms |
8172 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
