#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long
#define print(x) cout<<"["<<(x)<<"]"
#define se second
const int N = 5e4 + 5;
const ll mod = 1e9 + 7;
const ll P = 9973;
int n, a[N]; string s;
vector<int> adj[N];
/// hash:
ll pw[N];
void init(){
pw[0] = 1;
for (int i = 1; i <= n; i++)
pw[i] = pw[i - 1] * P % mod;
}
/// centroid:
int sz[N]; bool rip[N];
unordered_map<int, ll> hs[N], sh[N];
unordered_map<ll, int> fn[N];
int dfs(int p, int u){
sz[u] = 1;
for (auto c: adj[u]){
if (c == p || rip[c]) continue;
sz[u] += dfs(u, c);
}
return sz[u];
}
int centroid(int p, int u, int n_){
for (auto c: adj[u]){
if (c == p || rip[c]) continue;
if (sz[c] > n_/2) return centroid(u, c, n_);
}
return u;
}
void init_sh(int p, int u, int c, int d){
fn[c][hs[c][u]]++;
for (auto cc: adj[u]){
if (cc == p || rip[cc]) continue;
hs[c][cc] = (hs[c][u] * P + a[cc]) % mod;
sh[c][cc] = (sh[c][u] + (pw[d + 1] * a[cc]) % mod) % mod;
init_sh(u, cc, c, d + 1);
}
}
bool even, pass;
vector<int> st;
void dfs2(int p, int u, int c, int mid){
if (pass) return;
st.pb(u);
// sz + l = mid + 1
// l = mid - sz + 1
// sz - 1 - (mid - sz + 1) + 1 = i
// i = 2 * sz - mid - 1
int i = 2 * st.size() - mid - 1;
if ((even && i > 0) || (!even && i >= 0)){
if (hs[c][i] == sh[c][i]){
int v = st[i], pa = st[i - 1];
ll tmp = hs[c][u] - (hs[c][pa] * pw[(int)st.size() - i] % mod);
tmp = ((tmp % mod) + mod) % mod;
auto pilot = fn[c].find(tmp);
if (pilot != fn[c].end()){
if (i == 0){
if (pilot->se > 1) pass = true;
}else pass = true;
//print(c);print(u);print(i)<<'\n';pass = true;
}
}
}
for (auto v: adj[u]){
if (v == p || rip[v]) continue;
dfs2(u, v, c, mid);
}
st.pop_back();
}
void build(int p, int u, int mid){
int n_ = dfs(p, u);
int c = centroid(p, u, n_);
rip[c] = true; //print(c)<<'\n';
hs[c][c] = sh[c][c] = a[c];
init_sh(p, c, c, 0);
st.clear();
dfs2(p, c, c, mid);
if (pass) return;
for (auto v: adj[c]){
if (rip[v]) continue;
build(c, v, mid);
}
}
bool check(int val){
pass = false;
for (int i = 1; i <= n; i++){
hs[i].clear(); sh[i].clear();
fn[i].clear(); rip[i] = false;
}
build(0, 1, val);
return pass;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> s; init();
for (int i = 0; i < s.size(); i++)
a[i + 1] = (s[i] - 'a' + 1);
for (int i = 1; i < n; i++){
int u, v; cin >> u >> v;
adj[u].pb(v); adj[v].pb(u);
}
//return cout<<check(7),0;
int ans = 1;
int mid, left = 1, right = n / 2;
even = true;
while (left <= right){
mid = (left + right) / 2;
if (check(2*mid))
ans = max(ans,2*mid), left = mid + 1;
else right = mid - 1;
}
even = false;
left = 0, right = n / 2;
while (left <= right){
mid = (left + right) / 2;
if (check(2*mid+1))
ans = max(ans,2*mid+1), left = mid + 1;
else right = mid - 1;
}
cout << ans;
}
Compilation message
lampice.cpp: In function 'void dfs2(int, int, int, int)':
lampice.cpp:60:17: warning: unused variable 'v' [-Wunused-variable]
60 | int v = st[i], pa = st[i - 1];
| ^
lampice.cpp: In function 'int main()':
lampice.cpp:106:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
106 | for (int i = 0; i < s.size(); i++)
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
9940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5067 ms |
107552 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5080 ms |
109772 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
9940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
