#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e4 + 5;
const int mod = 1e9 + 7;
const int base = 131;
vector <int> g[maxn];
long long power[maxn], up[maxn], down[maxn];
int sub[maxn], dep[maxn];
bool vis[maxn];
char s[maxn];
void subtree(int x, int par) {
sub[x] = 1;
for(int i : g[x]) {
if(vis[i]) continue;
if(i != par) {
subtree(i, x);
sub[x] += sub[i];
}
}
}
int centroid(int x, int par, int range) {
for(int i : g[x]) {
if(vis[i]) continue;
if(i != par && sub[i] > range) {
return centroid(i, x, range);
}
}
return x;
}
void dfs(int x, int par) {
for(int i : g[x]) {
if(vis[i]) continue;
if(i != par) {
dep[i] = 1 + dep[x];
down[i] = (down[x] * base + s[i]) % mod;
up[i] = (power[dep[i]] * s[i] + up[x]) % mod;
dfs(i, x);
}
}
}
void getNode(int x, int par, vector <int> &node) {
node.push_back(x);
for(auto i : g[x]) {
if(!vis[i] && i != par) {
getNode(i, x, node);
}
}
}
unordered_set <int> table[maxn];
bool solve(int x, int k) {
subtree(x, 0);
x = centroid(x, 0, sub[x] / 2);
dep[x] = 0;
up[x] = down[x] = s[x];
dfs(x, 0);
bool ans = false;
for(int i : g[x]) {
if(vis[i]) continue;
vector <int> node;
vector <pair <int, int>> cont;
getNode(i, x, node);
for(auto j : node) {
if(dep[j] + 1 == k) {
ans |= (down[j] == up[j]);
} else if (dep[j] < k) {
long long value = (up[j] * power[k - dep[j] - 1] - down[j] + power[dep[j]] * s[x] + mod) % mod;
ans |= table[k - dep[j] - 1].find(value) != table[k - dep[j] - 1].end();
cont.emplace_back(dep[j], value);
}
}
for(auto j : cont) table[j.first].insert(j.second);
}
vector <int> node;
getNode(x, 0, node);
for(auto i : node) {
table[dep[i]].clear();
}
vis[x] = true;
for(int i : g[x]) {
if(vis[i]) continue;
ans |= solve(i, k);
}
return ans;
}
int main() {
int n;
scanf("%d", &n);
scanf("%s", s + 1);
power[0] = 1;
for(int i = 1; i <= n; i++) {
power[i] = (power[i - 1] * base) % mod;
}
for(int i = 1; i < n; i++) {
int p, q;
scanf("%d %d", &p, &q);
g[p].push_back(q);
g[q].push_back(p);
}
int ans;
int l = 1, r = (n + 1) / 2;
while(l < r) {
int mid = (l + r + 1) >> 1;
memset(vis, false, sizeof vis);
if(solve(1, 2 * mid - 1)) {
l = mid;
} else {
r = mid - 1;
}
}
ans = 2 * l - 1;
l = 1; r = (n / 2);
while(l < r) {
int mid = (l + r + 1) >> 1;
if(solve(1, mid * 2)) {
l = mid;
} else {
r = mid - 1;
}
}
ans = max(ans, l * 2);
printf("%d\n", ans);
return 0;
}
Compilation message
lampice.cpp: In function 'int main()':
lampice.cpp:90:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
lampice.cpp:91:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s", s + 1);
~~~~~^~~~~~~~~~~~~
lampice.cpp:98:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &p, &q);
~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
4352 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1362 ms |
12664 KB |
Output is correct |
| 2 |
Correct |
1622 ms |
13044 KB |
Output is correct |
| 3 |
Incorrect |
1892 ms |
13120 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2503 ms |
11816 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
4352 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
