#include <bits/stdc++.h>
#define d 256
#define MOD 1000000007
using namespace std;
/*
Avem un arbore cu n noduri, fiecare nod initial are o culoare.
Numim segment palindromic [u, v] daca lantul parcus de la u->v e acelasi cu cel parcus de la v->u
Trebuie sa gasim cel mai lung segment palindromic.
*/
const int NMAX(50005);
using ll = long long;
ll putH[NMAX], h[NMAX], rh[NMAX];
bool dead[NMAX];
int cul[NMAX], sz[NMAX], n, toSearch[NMAX], nr, cat[NMAX], cnt, dp[NMAX][18], dist[NMAX];
vector<int> G[NMAX], centroid, Grupa[NMAX];
bool viz[NMAX], can[NMAX];
inline void DFS(int nod)
{
cat[nod] = cnt;
viz[nod] = 1;
for(auto it: G[nod])
if(can[it] && !viz[it])
DFS(it);
}
inline int getCentroid(int nod)
{
viz[nod] = 1;
sz[nod] = 1;
int maxx = 0;
for(auto it: G[nod])
if(can[it] && !viz[it])
{
int c = getCentroid(it);
if(c != -1)
return c;
sz[nod] += sz[it];
maxx = max(maxx, sz[it]);
}
maxx = max(maxx, n - sz[nod]);
if(maxx <= n / 2)
return nod;
return -1;
}
inline void precalcCentroid(vector<int> nodes)
{
if(nodes.size() == 1)
{
centroid.push_back(nodes[0]);
return;
}
for(auto it: nodes)
can[it] = 1, viz[it] = 0;
int nd = getCentroid(nodes[0]);
centroid.push_back(nd);
for(auto it: nodes)
viz[it] = 0;
set<int> seac;
viz[nd] = 1;
cnt = 0;
for(auto it: G[nd])
if(can[it])
{
++cnt;
DFS(it);
}
vector<vector<int> > unde(cnt + 1);
for(auto it: nodes)
{
if(cat[it])
unde[cat[it]].push_back(it);
cat[it] = 0, can[it] = 0, viz[it] = 0;
}
int panaUnde = cnt;
for(int i = 1; i <= panaUnde; ++i)
precalcCentroid(unde[i]);
}
inline void Precalc(int nod, int tata, int lung, int baseV = 0)
{
for(int pt = 1; pt <= 17; ++pt)
dp[nod][pt] = dp[dp[nod][pt - 1]][pt - 1];
for(auto it: G[nod])
if(it != tata && !dead[it])
{
dist[it] = dist[nod] + 1;
h[it] = (d * h[nod] + cul[it]) % MOD;
rh[it] = (rh[nod] + cul[it] * putH[dist[it]]) % MOD;
dp[it][0] = nod;
int val = (baseV == 0 ? it : baseV);
Grupa[val].push_back(it);
Precalc(it, nod, lung, val);
}
}
inline ll getHash(int st, int dr){
return (h[dr] - h[st] * putH[dist[dr] - dist[st]] % MOD + MOD) % MOD;
}
int getDad(int nod, int dist){
for(int put = 17; put >= 0; --put)
if(dist - (1 << put) >= 0)
nod = dp[nod][put], dist -= (1 << put);
return nod;
}
inline bool calc(int nod, int lat)
{
if(lat <= 1)
return 1;
h[nod] = rh[nod] = cul[nod], dist[nod] = 0;
Precalc(nod, nod, lat);
set<ll> maiScurt, maiLung;
maiScurt.insert(0), maiLung.insert(0);
for(auto it: G[nod])
if(!dead[it])
{
for(auto nd: Grupa[it]){
int remDist = lat - dist[nd] - 1;
if(remDist < 0)
break;
if(remDist >= dist[nd]){
if(maiLung.count(getHash(nod, nd)))
return 1;
}
else {
int bucataPal = getDad(nd, remDist);
if(h[bucataPal] == rh[bucataPal] && maiScurt.count(getHash(bucataPal, nd)))
return 1;
}
}
for(auto nd: Grupa[it]){
int remDist = lat - dist[nd] - 1;
if(remDist < 0)
break;
if(remDist <= dist[nd])
{
int bucataPal = getDad(nd, remDist);
if(h[bucataPal] == rh[bucataPal])
maiLung.insert(getHash(bucataPal, nd));
}
else maiScurt.insert(getHash(nod, nd));
}
}
return 0;
}
inline bool solve(int lat)
{
for(int i = 1; i <= n; ++i)
dead[i] = 0;
for(auto cen: centroid)
{
bool ok = calc(cen, lat);
dead[cen] = 1;
if(ok)
return 1;
for(auto it: G[cen])
Grupa[it].clear();
}
return 0;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
string s;
cin >> n >> s;
vector<int> nodes;
for(int i = 0; i < n; ++i)
cul[i + 1] = s[i], nodes.push_back(i + 1);
for(int i = 1; i < n; ++i)
{
int x, y;
cin >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
putH[0] = 1;
for(int i = 1; i <= n; ++i)
putH[i] = putH[i - 1] * d % MOD;
precalcCentroid(nodes);
int st = 1, dr = n / 2 + 1, best = 1;
while(st <= dr)
{
int mij = (st + dr) / 2;
if(solve(2 * mij))
{
best = 2 * mij;
st = mij + 1;
}
else dr = mij - 1;
}
st = 1, dr = n / 2 + 1;
while(st <= dr)
{
int mij = (st + dr) / 2;
if(solve(2 * mij + 1))
{
best = 2 * mij + 1;
st = mij + 1;
}
else dr = mij - 1;
}
cout << best << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2676 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
414 ms |
13388 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1583 ms |
14912 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2676 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
