#include <bits/stdc++.h>
using namespace std;
vector<int> centree[50001], g[50001];
bool color[50001], seen[50001];
int depth[50001], dp[50001], pater[50001], pater2[50001], power[50001], inv[50001], up[50001], down[50001], rmq[50001][18], n, p = 31, mod = 1000000007;
multiset<int> hashes[50001];
string s;
int powmod(int a, int b) {
if (b == 0) {
return 1;
}
if (b % 2 == 1) {
return (1ll * a * powmod(a, b - 1));
}
int P = powmod(a, b / 2);
return (P * P) % mod;
}
int invers(int a) {
return powmod(a, mod - 2);
}
int get_size(int node, int parent) {
if (seen[node]) {
return 0;
}
dp[node] = 0;
for (auto i : g[node]) {
if (i != parent) {
dp[node] += get_size(i, node);
}
}
return ++dp[node];
}
int find_centroid(int node, int parent, int sz) {
for (auto i : g[node]) {
if (i != parent && !seen[i] && dp[i] > sz / 2) {
return find_centroid(i, node, sz);
}
}
return node;
}
void init_centroid(int node, int parent) {
int qui = find_centroid(node, 0, get_size(node, 0));
centree[parent].push_back(qui);
centree[qui].push_back(parent);
pater[qui] = parent;
seen[qui] = true;
for (auto i : g[qui]) {
if (!seen[i]) {
init_centroid(i, qui);
}
}
}
void paint(int node, bool flag) {
function<void(int, int)> dfs = [&](int node, int parent) {
color[node] = flag;
for (auto i : centree[node]) {
if (i != parent) {
dfs(i, node);
}
}
};
dfs(node, pater[node]);
}
void dfs(int node, int parent, int d) {
depth[node] = d;
pater2[node] = parent;
rmq[node][0] = parent;
for (int i = 1; i <= 17; ++i) {
rmq[node][i] = rmq[rmq[node][i - 1]][i - 1];
}
for (auto i : g[node]) {
if (i != parent) {
dfs(i, node, d + 1);
}
}
}
int anc(int node, int k) {
for (int i = 17; i >= 0; --i) {
if (k & (1 << i)) {
node = rmq[node][i];
k -= (1 << i);
}
}
return node;
}
int get_depth(int node, int root) {
return depth[node] - depth[root];
}
void compute_powers() {
power[0] = 1;
for (int i = 1; i <= 50000; ++i) {
power[i] = (1ll * power[i - 1] * p) % mod;
}
int invp = invers(p);
inv[0] = 1;
for (int i = 1; i <= 50000; ++i) {
inv[i] = (1ll * inv[i - 1] * invp) % mod;
}
}
void compute_up(int root) {
function<void(int, int, int)> dfs = [&](int node, int parent, int hash) {
if (!color[node]) {
return;
}
up[node] = ((1ll * hash * p) % mod + (s[node] - 'a' + 1)) % mod;
for (auto i : g[node]) {
if (i != parent) {
dfs(i, node, up[node]);
}
}
};
dfs(root, 0, 0);
}
void compute_down(int root) {
function<void(int, int, int)> dfs = [&](int node, int parent, int hash) {
if (!color[node]) {
return;
}
down[node] = hash + power[get_depth(node, root)] * (s[node] - 'a' + 1);
for (auto i : g[node]) {
if (i != parent) {
dfs(i, node, up[node]);
}
}
};
dfs(root, 0, 0);
}
int hashup(int a, int b, int root) { // b e stramos al lui a !!!!
if (b == root) {
return up[a];
}
else {
return (up[a] - (1ll * up[pater2[b]] * power[get_depth(a, root) - get_depth(b, root) + 1]) % mod + mod) % mod;
}
}
int hashdown(int a, int b, int root) {
if (b == root) {
return down[a];
}
return (1ll * (down[a] - down[b] + mod) % mod * inv[get_depth(b, root)]) % mod;
}
bool palindrome(int a, int b, int root) {
return hashup(a, b, root) == hashdown(a, b, root);
}
bool check(int root, int length) {
paint(root, 1);
function<void(int, int, int)> update = [&](int node, int parent, int d) {
if (!color[node]) {
return;
}
depth[node] = d;
pater2[node] = parent;
rmq[node][0] = parent;
for (int i = 1; i <= 17; ++i) {
rmq[node][i] = rmq[rmq[node][i - 1]][i - 1];
}
for (auto i : g[node]) {
if (i != parent) {
update(i, node, d + 1);
}
}
};
update(root, root, 0);
compute_up(root);
compute_down(root);
function<void(int, int, int)> add = [&](int node, int parent, int subtree) {
if (!color[node]) {
return;
}
hashes[get_depth(node, root)].insert(hashup(node, subtree, root));
for (auto i : g[node]) {
if (i != parent) {
add(i, node, subtree);
}
}
};
function<void(int, int, int)> rem = [&](int node, int parent, int subtree) {
if (!color[node]) {
return;
}
hashes[get_depth(node, root)].erase(hashes[get_depth(node, root)].find(hashup(node, subtree, root)));
for (auto i : g[node]) {
if (i != parent) {
rem(i, node, subtree);
}
}
};
function<bool(int, int)> dfs = [&](int node, int parent) {
if (!color[node]) {
return false;
}
int d = get_depth(node, root) + 1;
int req = length - d;
bool ans = false;
if (req > 0 && d >= req) {
int hash = hashup(node, root, root);
if (d == req) {
ans = hashes[req].find(hash) != hashes[req].end();
}
else {
int qui = anc(node, req);
hash = hashup(node, anc(node, req - 1), root);
ans = hashes[req].find(hash) != hashes[req].end() && palindrome(qui, root, root);
}
}
for (auto i : g[node]) {
if (i != parent) {
ans |= dfs(i, node);
}
}
return ans;
};
function<bool(int, int)> dfs2 = [&](int node, int parent) {
if (!color[node]) {
return false;
}
int d = get_depth(node, root) + 1;
bool ok = false;
if (d == length) {
ok = palindrome(node, root, root);
}
for (auto i : g[node]) {
if (i != parent) {
ok |= dfs2(i, node);
}
}
return ok;
};
bool ans = false;
for (auto i : g[root]) {
add(i, root, i);
}
for (auto i : g[root]) {
rem(i, root, i);
ans |= dfs(i, root);
add(i, root, i);
}
ans |= dfs2(root, 0);
for (auto i : g[root]) {
rem(i, root, i);
}
paint(root, 0);
return ans;
}
bool check_centroids(int length) {
for (int i = 1; i <= n; ++i) {
if (check(i, length)) {
return true;
}
}
return false;
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
cin >> n >> s;
s = '$' + s; // nu sunt colcalar
for (int i = 1; i < n; ++i) {
int x, y;
cin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
init_centroid(1, 0);
dfs(1, 1, 0);
compute_powers();
int st = 1, dr = n, rep1 = 0, rep2 = 0;
while (st <= dr) {
int mid = (st + dr) / 2;
if (check_centroids(2 * mid)) {
rep1 = mid;
st = mid + 1;
}
else {
dr = mid - 1;
}
}
st = 1, dr = n;
while (st <= dr) {
int mid = (st + dr) / 2;
if (check_centroids(2 * mid + 1)) {
rep2 = mid;
st = mid + 1;
}
else {
dr = mid - 1;
}
}
cout << max({ rep1 * 2,rep2 * 2 + 1 });
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
5444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5103 ms |
17484 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5095 ms |
17196 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
5444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
