#include <cmath>
#include <iostream>
#include <set>
#include <climits>
#include <cstdio>
#include <algorithm>
#include <cassert>
#include <string>
#include <vector>
#include <iomanip>
#include <unordered_map>
#include <type_traits>
#include <string>
#include <queue>
#include <map>
using namespace std;
const int MOD = 1e9 + 9;
const int BASE = 293;
const int inv = 706484648;
class Tree {
public:
vector<int> sub, depth, parent;
vector<int64_t> dp1, dp2;
vector<bool> hasVisited;
vector<int> adj[(int)5e4];
vector<int64_t> powr, ipowr;
int dp[(int)5e4][17];
string s;
int sz;
int dfs1 (int curNode, int prevNode) {
sub[curNode] = 1;
for (int i: adj[curNode]) if (!hasVisited[i] && i != prevNode) sub[curNode] += dfs1(i, curNode);
return (sz = sub[curNode]);
}
int get_centroid (int curNode, int prevNode) {
for (int i: adj[curNode]) if (!hasVisited[i] && i != prevNode && sub[i] > sz/2) return get_centroid(i, curNode);
return curNode;
}
int max_len; int fine = 0;
void fill (int curNode, int prevNode, int d, int64_t val1, int64_t val2) {
dp1[curNode] = val1 = (BASE * val1 + s[curNode]) % MOD;
dp2[curNode] = val2 = (powr[d] * s[curNode] + val2) % MOD;
fine += (dp1[curNode] == dp2[curNode] && d + 1 == max_len);
dp[curNode][0] = prevNode;
for (int i = 1; i < 17; i++) {
dp[curNode][i] = dp[dp[curNode][i - 1]][i - 1];
}
depth[curNode] = d;
parent[curNode] = prevNode;
for (int i: adj[curNode]) {
if (!hasVisited[i] && i != prevNode) {
fill(i, curNode, d + 1, val1, val2);
}
}
}
int64_t go_up (int l, int d) {
while (d) {
l = dp[l][(int)log2(d & -d)];
d -= (d & -d);
}
return l;
}
int centroid;
int get1 (int l, int r) {
return (dp1[r] - (powr[depth[r] - depth[l] + 1] * dp1[parent[l]]) % MOD + MOD) % MOD;
}
set<int> m1;
vector<int> to_do;
void dfs (int curNode, int prevNode) {
if (depth[curNode] + 1 >= max_len) {
return;
}
to_do.push_back(dp1[curNode]);
//m1[dp1[curNode]]++, v1[dp1[curNode]]++;
if (2 * depth[curNode] + 1 >= max_len) {
int x = go_up(curNode, max_len - depth[curNode] - 2);
if (dp1[parent[x]] == dp2[parent[x]]) {
if (m1.count((get1(x, curNode) + powr[max_len - depth[curNode] - 1] * s[centroid]) % MOD)) {
fine ++;
return;
}
}
}
for (int i: adj[curNode]) {
if (i != prevNode && !hasVisited[i]) {
dfs (i, curNode);
}
}
}
bool solve (int curNode) {
dfs1(curNode, curNode);
centroid = get_centroid(curNode, curNode);
hasVisited[centroid] = true;
depth[centroid] = 0;
for (int i = 0; i < 17; i++) dp[centroid][i] = centroid;
dp1[centroid] = s[centroid], dp2[centroid] = s[centroid];
fine += (max_len == 1);
for (int i: adj[centroid]) {
if (!hasVisited[i]) {
fill(i, centroid, 1, s[centroid], s[centroid]);
}
}
m1.clear();
for (int i: adj[centroid]) {
if (!hasVisited[i]) {
dfs (i, centroid);
for (int j: to_do) m1.insert(j);
to_do.clear();
}
}
if (fine) return true;
reverse(adj[centroid].begin(), adj[centroid].end());
m1.clear();
for (int i: adj[centroid]) {
if (!hasVisited[i]) {
dfs (i, centroid);
for (int j: to_do) m1.insert(j);
to_do.clear();
}
}
if (fine) return true;
for (int i: adj[centroid]) {
if (!hasVisited[i]) {
if (solve(i)) {
return true;
}
}
}
return false;
}
Tree (int n) {
sub.resize(n), hasVisited.assign(n, false); powr.push_back(1); for (int i = 0; i <= n + 5; i++) powr.push_back(powr.back() * BASE), powr.back() %= MOD;
ipowr.push_back(1); for (int i = 0; i <= n + 5; i++) ipowr.push_back(ipowr.back() * inv), powr.back() %= MOD;
parent.resize(n), depth.resize(n), dp1.resize(n), dp2.resize(n);
}
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n; cin >> n;
string s; cin >> s;
Tree myTree(n);
for (int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
u--, v--;
myTree.adj[u].push_back(v), myTree.adj[v].push_back(u);
}
myTree.s = s;
int myMax = 0;
int l = 0;
int r = s.length()/2;
while (l != r) {
int m = (l + r + 1)/2;
myTree.max_len = 2 * m; myTree.fine = 0; myTree.hasVisited.assign(n, false);
myTree.solve(0);
if (myTree.fine) {
l = m;
} else {
r = m - 1;
}
}
myMax = max(myMax, 2 * l); l = 0;
r = s.length()/2;
while (l < r) {
int m = (l + r + 1)/2;
myTree.max_len = 2 * m + 1; myTree.fine = 0; myTree.hasVisited.assign(n, false);
myTree.solve(0);
if (myTree.fine) {
l = m;
} else {
r = m - 1;
}
}
myMax = max(myMax, 2 * l + 1);
cout << myMax;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
4820 KB |
Output is correct |
| 2 |
Correct |
20 ms |
4904 KB |
Output is correct |
| 3 |
Correct |
60 ms |
4996 KB |
Output is correct |
| 4 |
Correct |
61 ms |
4948 KB |
Output is correct |
| 5 |
Correct |
2 ms |
4692 KB |
Output is correct |
| 6 |
Correct |
3 ms |
4692 KB |
Output is correct |
| 7 |
Correct |
2 ms |
4792 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3656 ms |
12000 KB |
Output is correct |
| 2 |
Correct |
3761 ms |
12136 KB |
Output is correct |
| 3 |
Correct |
2530 ms |
12360 KB |
Output is correct |
| 4 |
Correct |
2813 ms |
12808 KB |
Output is correct |
| 5 |
Correct |
4160 ms |
13092 KB |
Output is correct |
| 6 |
Correct |
535 ms |
12032 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5059 ms |
11596 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
4820 KB |
Output is correct |
| 2 |
Correct |
20 ms |
4904 KB |
Output is correct |
| 3 |
Correct |
60 ms |
4996 KB |
Output is correct |
| 4 |
Correct |
61 ms |
4948 KB |
Output is correct |
| 5 |
Correct |
2 ms |
4692 KB |
Output is correct |
| 6 |
Correct |
3 ms |
4692 KB |
Output is correct |
| 7 |
Correct |
2 ms |
4792 KB |
Output is correct |
| 8 |
Correct |
3656 ms |
12000 KB |
Output is correct |
| 9 |
Correct |
3761 ms |
12136 KB |
Output is correct |
| 10 |
Correct |
2530 ms |
12360 KB |
Output is correct |
| 11 |
Correct |
2813 ms |
12808 KB |
Output is correct |
| 12 |
Correct |
4160 ms |
13092 KB |
Output is correct |
| 13 |
Correct |
535 ms |
12032 KB |
Output is correct |
| 14 |
Execution timed out |
5059 ms |
11596 KB |
Time limit exceeded |
| 15 |
Halted |
0 ms |
0 KB |
- |
