#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<long long, long long>;
#define pb push_back
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
#define int long long
const ll N = 3e5 + 100;
const ll inf = 1e18;
const ll mod = 1e9 + 7;
const ll block = 520;
const ll base = 35711;
vector<int>adj[N];
int n, cur_sz; string s;
int sz[N]; bool vs[N];
ll hsh[N], pw[N];
unordered_map<int,int>mp;
int ans = 0;
void get_sz(int u, int par){
sz[u] = 1;
for(auto v : adj[u]){
if(v == par || vs[v]) continue;
get_sz(v, u);
sz[u] += sz[v];
}
}
int find_cen(ll u, ll par){
for(auto v : adj[u]){
if(v == par || vs[v]) continue;
if(sz[v] > cur_sz / 2) return find_cen(v, u);
}
return u;
}
int get_cen(ll v){
get_sz(v, 0);
cur_sz = sz[v];
return find_cen(v, 0);
}
void add(ll u, ll par, ll cur){
cur = ((cur * base) + (s[u] - 'a' + 1)) % mod;
mp[cur]++;
for(auto v : adj[u]){
if(v == par || vs[v]) continue;
add(v, u, cur);
}
}
void del(ll u, ll par, ll cur){
cur = ((cur * base) + (s[u] - 'a' + 1)) % mod;
mp[cur]--;
for(auto v : adj[u]){
if(v == par || vs[v]) continue;
del(v, u, cur);
}
}
int get_hash(int l, int r){
return (hsh[r] - hsh[l - 1] * pw[r - l + 1] + mod * mod) % mod;
}
bool dfs(int u, int par, int d, int len, ll cur){
cur = ((cur * base) + (s[u] - 'a' + 1)) % mod;
if(d > len) return 0;
hsh[d] = ((hsh[d-1] * base) + (s[u] - 'a' + 1)) % mod;
if(d >= len / 2 + len % 2){
ll r = d, l = (d - (len - d) + 1);
ll tmp = get_hash(l, r);
if(mp[tmp]) return 1;
}
if(d == len / 2){
if(mp[cur]) return 1;
}
for(auto v : adj[u]){
if(v == par || vs[v]) continue;
if(dfs(v, u, d + 1, len, cur)) return 1;
}
return 0;
}
void centroid(ll u){
vs[u] = 1;
int l = 0, r = n + 1;
add(u, 0, 0);
while(l + 1 < r){
int mid = (l + r) / 2;
bool ck = 0;
for(auto v : adj[u]){
if(vs[v]) continue;
del(v, u, (s[u] - 'a' + 1));
if(mid + 1 <= min(n, r)){
if(dfs(v, u, 1, mid + 1, (s[u] - 'a' + 1))){
ck = 1;
l = mid + 1;
}
}
if(mid <= min(n, r) && !ck){
if(dfs(v, u, 1, mid, (s[u] - 'a' + 1))){
ck = 1;
l = mid;
}
}
add(v, u, (s[u] - 'a' + 1));
if(ck) break;
}
if(!ck) r = mid;
}
ans = max(ans, l);
for(auto v : adj[u]){
if(vs[v]) continue;
ll nxt = get_cen(v);
centroid(nxt);
}
}
void to_nho_cau(){
cin >> n >> s;
s = " " + s;
pw[0] = 1;
for(int i = 1; i <= n + 1;i++) pw[i] = (pw[i-1] * base) % mod;
for(int i = 1; i <= n - 1;i++){
ll u,v; cin >> u >> v;
adj[u].pb(v);
adj[v].pb(u);
}
ll root = get_cen(1);
centroid(root);
cout << ans << '\n';
}
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
//cin >> t;
while(t--) to_nho_cau();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
10588 KB |
Output is correct |
| 2 |
Correct |
7 ms |
10588 KB |
Output is correct |
| 3 |
Incorrect |
13 ms |
11360 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2534 ms |
112188 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2391 ms |
98256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
10588 KB |
Output is correct |
| 2 |
Correct |
7 ms |
10588 KB |
Output is correct |
| 3 |
Incorrect |
13 ms |
11360 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
