#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
using namespace std;
typedef long long ll;
const int maxn = 5e4 + 5, base = 131, mod = 1e9 + 7;
vector<int> adj[maxn];
int par[maxn][17], sz[maxn];
int N; string str;
int depth[maxn];
int POW[maxn];
ll HashUp[maxn], HashDown[maxn];
bool vis[maxn], ret;
vector<int> node;
int tin[maxn], tout[maxn], nTime;
vector<pair<int, int>> same[maxn];
void findsz(int u, int p)
{
sz[u] = 1;
for (int v : adj[u]){
if (v == p || vis[v] == true) continue;
findsz(v, u);
sz[u] += sz[v];
}
}
void prepare(int u, int p)
{
node.pb(u);
tin[u] = ++nTime;
same[depth[u]].pb(mp(HashDown[u], u));
for (int i = 1; (1 << i) <= N; ++i)
par[u][i] = par[par[u][i - 1]][i - 1];
for (int v : adj[u]){
if (v == p || vis[v] == true) continue;
par[v][0] = u;
depth[v] = depth[u] + 1;
HashDown[v] = (HashDown[u] * base + str[v] - 'a' + 1) % mod;
HashUp[v] = (HashUp[u] + POW[depth[v] - 1] * (str[v] - 'a' + 1)) % mod;
prepare(v, u);
}
tout[u] = nTime;
}
bool inside(int u, int v)
{
return tin[u] <= tin[v] && tout[v] <= tout[u];
}
int findcen(int u, int p, int need)
{
for (int v : adj[u]){
if (v == p || vis[v] == true) continue;
if (sz[v] > need / 2) return findcen(v, u, need);
}
return u;
}
int lift(int x, int y)
{
for (int k = 16; k >= 0; --k){
if (y >> k & 1) x = par[x][k];
}
return x;
}
int LCA(int x, int y)
{
if (depth[x] < depth[y]) swap(x, y);
if (inside(y, x)) return y;
for (int k = 16; k >= 0; --k){
if (depth[par[x][k]] >= depth[y]){
x = par[x][k];
}
}
if (x == y) return x;
for (int k = 16; k >= 0; --k){
if (par[x][k] != par[y][k]){
x = par[x][k];
y = par[y][k];
}
}
return par[x][0];
}
int GetHash(int u, int v)
{
return (HashDown[u] - 1ll * HashDown[par[v][0]] * POW[depth[u] - depth[v] + 1] + mod) % mod;
}
void solve(int u, int len)
{
if (ret) return;
HashDown[u] = str[u] - 'a' + 1;
HashUp[u] = str[u] - 'a' + 1;
node.clear();
par[u][0] = 0; depth[u] = 1; nTime = 0;
prepare(u, u);
for (int i = 1; i <= N; ++i){
if (same[i].empty()) break;
sort(same[i].begin(), same[i].end());
}
for (int A : node){
if (ret) break;
int dneed = len - depth[A] + 1;
if (dneed > depth[A] || dneed < 1) continue;
int C = lift(A, dneed - 1);
if (HashDown[C] != HashUp[C]) continue;
int hneed = GetHash(A, C);
int l = lower_bound(same[dneed].begin(), same[dneed].end(), mp(hneed, -1)) - same[dneed].begin();
if (l == (int)same[dneed].size() || same[dneed][l].fi != hneed) continue;
while (l < (int)same[dneed].size()){
if (same[dneed][l].fi != hneed) break;
int B = same[dneed][l].se;
///cerr << A << ' ' << B << '\n';
if (LCA(A, B) == u){
ret = true;
break;
}
else ++l;
}
}
for (int i = 1; i <= N; ++i){
if (same[i].empty()) break;
same[i].clear();
}
}
void centroid(int root, int len)
{
findsz(root, root);
int u = findcen(root, root, sz[root]);
vis[u] = true;
solve(u, len);
for (int v : adj[u]){
if (vis[v] == false){
centroid(v, len);
}
}
}
bool check(int len, int ok)
{
len = len * 2 + ok;
ret = false;
for (int i = 1; i <= N; ++i) vis[i] = false;
centroid(1, len);
return ret;
}
signed main(void)
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
if (fopen("A.INP", "r")){
freopen("A.INP", "r", stdin);
freopen("A.OUT", "w", stdout);
}
cin >> N >> str; str = " " + str;
for (int i = 1; i < N; ++i){
int u, v; cin >> u >> v;
adj[u].pb(v); adj[v].pb(u);
}
POW[0] = 1;
for (int i = 1; i <= N; ++i)
POW[i] = 1ll * POW[i - 1] * base % mod;
int l = 0, r = N / 2, mid;
while (l <= r){
mid = (l + r) / 2;
if (check(mid, 1)) l = mid + 1;
else r = mid - 1;
}
int res = (r * 2 + 1);
l = 1, r = N / 2, mid;
while (l <= r){
mid = (l + r) / 2;
if (check(mid, 0)) l = mid + 1;
else r = mid - 1;
}
res = max(res, r * 2);
cout << res << '\n';
}
Compilation message
lampice.cpp: In function 'int main()':
lampice.cpp:180:24: warning: right operand of comma operator has no effect [-Wunused-value]
l = 1, r = N / 2, mid;
^
lampice.cpp:162:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen("A.INP", "r", stdin);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~
lampice.cpp:163:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen("A.OUT", "w", stdout);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
10 ms |
2808 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2045 ms |
12744 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
5081 ms |
11764 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
10 ms |
2808 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
