#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int nmax = 5e4 + 5;
#define int ll
#define hash isdoaohhdkgf
const int mod = 1e9 + 9;
int p[nmax][2];
struct hash {
int v[2], len;
hash() {
v[0] = v[1] = len = 0;
}
hash(char ch) {
ch -= 'a' - 1;
v[0] = ch, v[1] = ch, len = 1;
}
hash(int a, int b, int c) {
v[0] = a, v[1] = b, len = c;
}
hash operator + (const hash& x) const {
return hash((v[0] * p[x.len][0] + x.v[0]) % mod,
(v[1] * p[x.len][1] + x.v[1]) % mod,
len + x.len);
}
void operator +=(const hash& x) {*this = *this + x;}
void operator +=(const char& x) {*this = *this + hash(x);}
bool operator == (const hash& x) {return v[0] == x.v[0] && v[1] == x.v[1] && len == x.len;}
hash operator -(const hash& x) const {
return hash(((v[0] - x.v[0] * p[len - x.len][0] % mod + mod) % mod),
((v[1] - x.v[1] * p[len - x.len][1] % mod + mod) % mod),
len - x.len);
}
ll operator()() const {
return v[0] * mod + v[1];
}
};
char ch[nmax];
int n;
vector<int> g[nmax];
#undef int
namespace READ {
void init() {
p[0][0] = 1;
p[0][1] = 1;
p[1][1] = 37;
p[1][0] = 666013;
for(int i = 2; i < nmax; i++)
p[i][0] = (p[i - 1][0] * p[1][0]) % mod, p[i][1] = (p[i - 1][1] * p[1][1]) % mod;
}
void read() {
cin >> n;
for(int i = 1; i <= n; i++)
cin >> ch[i];
for(int i = 1, x, y; i < n; i++) {
cin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
}
}
namespace CENTROID {
bool merge = 0;
int lim = 0;
int area[nmax];
int iscentr[nmax];
unordered_multiset<ll> ms;
int depth[nmax];
int ispal[nmax];
int mkarea(int node, int f) {
ispal[node] = 0;
if(iscentr[node])
return 0;
area[node] = 1;
for(auto x : g[node]) {
if(x == f)
continue;
area[node] += mkarea(x, node);
}
return area[node];
}
int getcentroid(int node, int f, int limit) {
for(auto x : g[node]) {
if(iscentr[x] || x == f)
continue;
if(area[x] >= limit / 2)
return getcentroid(x, node, limit);
}
return node;
}
void upd(int node, int f, bool aggr, hash h = hash()) {
depth[node] = depth[f] + 1;
h += ch[node];
if(aggr)
ms.insert(h());
else
ms.erase(h());
for(auto x : g[node]) {
if(x == f || iscentr[x])
continue;
upd(x, node, aggr, h);
}
return;
}
int st[nmax], ptr = 0;
hash mst[nmax];
void oper(int node, int f, hash fr = hash(), hash bk = hash()) {
fr = fr + hash(ch[node]);
bk = hash(ch[node]) + bk;
mst[ptr] = fr;
st[ptr++] = node;
if(ptr <= lim) {
if(fr == bk)
ispal[node] = 1;
if(ptr == lim && ispal[node])
merge = 1;
else {
int k = 2 * ptr - 1 - lim;
if(k >= 0) {
if(ms.count((fr - mst[k])()) && ispal[st[k]])
merge = 1;
}
}
for(auto x : g[node]) {
if(x == f || iscentr[x])
continue;
oper(x, node, fr, bk);
}
}
ptr--;
}
void mkcentroid(int node) {
mkarea(node, node);
int root = getcentroid(node, node, area[node]);
iscentr[root] = 1;
node = root;
ispal[root] = 1;
for(auto x : g[root])
upd(x, node, 1);
ptr = 0;
depth[node] = 0;
mst[ptr] = hash(ch[root]);
st[ptr++] = root;
for(auto x : g[root]) {
if(iscentr[x])
continue;
upd(x, node, 0);
oper(x, node, hash(ch[root]), hash(ch[root]));
upd(x, node, 1);
}
ms.erase(ms.begin(), ms.end());
for(auto x : g[root]) {
if(!iscentr[x])
mkcentroid(x);
}
ms.erase(ms.begin(), ms.end());
}
bool query(int len) {
ms.erase(ms.begin(), ms.end());
fill(iscentr, iscentr + n + 1, 0);
lim = len;
merge = 0;
mkcentroid(1);
//cout << "----------------------\n";
return merge;
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
READ::init();
READ::read();
int temp, imp = 1, ev = 0;
for(int i = 18; i > 0; i--) {
if(CENTROID::query(imp + (1 << i)))
imp += (1 << i);
}
for(int i = 18; i > 0; i--) {
if(CENTROID::query(ev + (1 << i)))
ev += (1 << i);
}
cout << max(imp, ev) << '\n';
}
Compilation message
lampice.cpp: In function 'int main()':
lampice.cpp:179:7: warning: unused variable 'temp' [-Wunused-variable]
179 | int temp, imp = 1, ev = 0;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
3664 KB |
Output is correct |
| 2 |
Correct |
67 ms |
3532 KB |
Output is correct |
| 3 |
Correct |
163 ms |
3532 KB |
Output is correct |
| 4 |
Incorrect |
221 ms |
3660 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5095 ms |
10972 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5063 ms |
9556 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
3664 KB |
Output is correct |
| 2 |
Correct |
67 ms |
3532 KB |
Output is correct |
| 3 |
Correct |
163 ms |
3532 KB |
Output is correct |
| 4 |
Incorrect |
221 ms |
3660 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
