/*
www.youtube.com/YugiHackerChannel
linktr.ee/YugiHacker
*/
#include<bits/stdc++.h>
#define el cout<<"\n"
#define f0(i,n) for(int i=0;i<n;++i)
#define f1(i,n) for(int i=1;i<=n;++i)
#define maxn 50004
#define base 31
#define MOD 1000000007
using namespace std;
int n;
long long pw[maxn];
string s;
vector <int> a[maxn];
int sz[maxn], del[maxn];
void dfs_sz(int u, int p=-1) {
sz[u] = 1;
for (int v:a[u]) if (v != p && !del[v]) dfs_sz(v, u), sz[u] += sz[v];
}
int get_centroid(int u, int p, int n) {
for (int v:a[u]) if (v != p && !del[v] && sz[v] * 2 > n) return get_centroid(v, u, n);
return u;
}
int ma;
map <long long, int> mp[maxn];
bool dfs(int u, int p, int h, int len, long long H_up, long long H_down, bool update) {
if (h > len) return 0;
ma = max(ma, h);
H_up = (H_up + (s[u] - 'a' + 1) * pw[h-1]) % MOD;
H_down = (H_down * base + s[u] - 'a' + 1) % MOD;
long long H = (H_up * pw[len - h] - H_down + MOD) % MOD;
if (update) mp[h][H] = 1;
else {
if (mp[len - h - 1].count(H)) return 1;
}
for (int v:a[u]) if (v != p && !del[v])
if (dfs(v, u, h+1, len, H_up, H_down, update)) return 1;
return 0;
}
bool CentroidDecomposition(int u, int len) {
dfs_sz(u);
u = get_centroid(u, -1, sz[u]);
del[u] = 1;
long long H_down = s[u] - 'a' + 1;
long long H_up = 0;
long long H = (H_up * pw[len] - H_down + MOD) % MOD;
mp[0][H] = 1;
for (int v:a[u]) if (!del[v])
{
if (dfs(v, u, 1, len, H_up, H_down, 0)) return 1;
dfs(v, u, 1, len, H_up, H_down, 1);
}
f0 (i, ma + 1) mp[i].clear();
for (int v:a[u]) if (!del[v]) if (CentroidDecomposition(v, len)) return 1;
return 0;
}
bool check (int len) {
f1 (u, n) del[u] = 0;
f0 (i, ma + 1) mp[i].clear();
return CentroidDecomposition(1, len);
}
main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> n >> s;
pw[0] = 1;
for (int i=1; i<=n; i++) pw[i] = pw[i-1] * base % MOD;
s = ' ' + s;
f1 (i, n-1) {
int u, v; cin >> u >> v;
a[u].push_back(v);
a[v].push_back(u);
}
int ans = 1;
int l = 0, r = n/2+1;
while (r - l > 1) {
int m = (l + r) / 2;
if (check(m*2)) l = m;
else r = m;
}
ans = max(ans, l * 2);
l = 0, r = n/2+1;
while (r - l > 1) {
int m = (l + r) / 2;
if (check(m*2+1)) l = m;
else r = m;
}
ans = max(ans, l * 2 + 1);
cout << ans;
}
Compilation message
lampice.cpp:69:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
69 | main()
| ^~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4688 KB |
Output is correct |
2 |
Runtime error |
9 ms |
9296 KB |
Execution killed with signal 11 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
22 ms |
19468 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
1094 ms |
21540 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4688 KB |
Output is correct |
2 |
Runtime error |
9 ms |
9296 KB |
Execution killed with signal 11 |
3 |
Halted |
0 ms |
0 KB |
- |