#include <bits/stdc++.h>
using namespace std;
const int kN = 5e4;
const int mod = 1e9 + 9;
const int base = 29;
string s;
vector<int> g[1 + kN];
int p[1 + kN], sz[1 + kN], h1[1 + kN], h2[1 + kN];
vector<int> centroids, nodes;
bitset<1 + kN> vis;
unordered_multiset<int> prefs;
void addSelf(int &x, const int &y) {
x += y;
if (x >= mod) {
x -= mod;
}
}
int add(int x, const int &y) {
addSelf(x, y);
return x;
}
void multSelf(int &x, const int &y) {
x = (int64_t)x * y % mod;
}
int mult(int x, const int &y) {
multSelf(x, y);
return x;
}
void precalc() {
p[0] = 1;
for (int i = 1; i <= kN; ++i) {
p[i] = mult(p[i - 1], base);
}
}
void findSize(int u, int par) {
sz[u] = 1;
for (int v : g[u]) {
if (!vis[v] && v != par) {
findSize(v, u);
sz[u] += sz[v];
}
}
}
int findCentroid(int u, int par, int n) {
for (int v : g[u]) {
if (!vis[v] && v != par && sz[v] > n / 2) {
return findCentroid(v, u, n);
}
}
return u;
}
void dfs1(int u, int par, int depth) {
h1[u] = add(mult(h1[par], base), s[u] - 'a' + 1);
h2[u] = add(h2[par], mult(p[depth], s[u] - 'a' + 1));
prefs.emplace(h1[u]);
for (int v : g[u]) {
if (!vis[v] && v != par) {
dfs1(v, u, depth + 1);
}
}
}
void modifyPaths(int u, int par, bool t) {
if (t) {
prefs.emplace(h1[u]);
} else {
prefs.erase(prefs.find(h1[u]));
}
for (int v : g[u]) {
if (!vis[v] && v != par) {
modifyPaths(v, u, t);
}
}
}
bool dfs2(int u, int par, int depth, int len) {
if (depth == len) {
return h1[u] == h2[u];
}
nodes.emplace_back(u);
int d = len - depth + 1;
if (d <= depth) {
int split = nodes[nodes.size() - d];
if (h1[split] == h2[split]) {
split = nodes[nodes.size() - d - 1];
int hsh = add(h1[u], mod - mult(p[d], h1[split]));
if (prefs.count(hsh)) {
return true;
}
}
}
for (int v : g[u]) {
if (!vis[v] && v != par && dfs2(v, u, depth + 1, len)) {
return true;
}
}
nodes.pop_back();
return false;
}
void build(int u) {
findSize(u, 0);
int c = findCentroid(u, 0, sz[u]);
centroids.emplace_back(c);
vis[c] = true;
for (int v : g[c]) {
if (!vis[v]) {
build(v);
}
}
}
bool solve(int u, int len) {
for (int c : centroids) {
prefs.clear();
dfs1(c, 0, 0);
for (int v : g[c]) {
if (!vis[v]) {
modifyPaths(v, c, false);
nodes.clear();
nodes.emplace_back(0);
nodes.emplace_back(c);
if (dfs2(v, c, 2, len)) {
return true;
}
modifyPaths(v, c, true);
}
}
vis[c] = true;
}
return false;
}
bool check(int n, int len) {
bool ret = true;
for (int v = 1; v <= n; ++v) {
vis[v] = false;
}
return ret;
}
void testCase() {
int n;
cin >> n >> s;
s = '$' + s;
bool ok2 = false;
for (int i = 1; i < n; ++i) {
int u, v;
cin >> u >> v;
g[u].emplace_back(v);
g[v].emplace_back(u);
if (s[u] == s[v]) {
ok2 = true;
}
}
build(1);
for (int v = 1; v <= n; ++v) {
vis[v] = false;
}
int l = 1, r = (n - 1) / 2, ans1 = 1;
while (l <= r) {
int mid = (l + r) / 2;
if (check(n, 2 * mid + 1)) {
ans1 = 2 * mid + 1;
l = mid + 1;
} else {
r = mid - 1;
}
}
int ans2 = 0;
l = 2, r = n / 2;
while (l <= r) {
int mid = (l + r) / 2;
if (check(n, 2 * mid)) {
ans2 = 2 * mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
cout << max({1 + ok2, ans1, ans2}) << '\n';
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
precalc();
int tests = 1;
for (int tc = 0; tc < tests; ++tc) {
testCase();
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1612 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
6292 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
40 ms |
4556 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1612 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
