#ifdef LOCAL
#include "local.h"
#else
#include <bits/stdc++.h>
#define debug(...)
#define DB(...)
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#endif
using namespace std;
static const bool __initialization = []() {
cin.tie(nullptr)->sync_with_stdio(false);
#define TASK "empty"
if (fopen(TASK".inp", "r")) {
(void)(!freopen(TASK".inp", "r", stdin));
(void)(!freopen(TASK".out", "w", stdout)); }
return true;
}();
using ll = long long;
using ld = long double;
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define For(i, l, r) for (int i = (l); i <= (r); ++i)
#define Ford(i, r, l) for (int i = (r); i >= (l); --i)
#define Rep(i, n) For (i, 0, (n) - 1)
#define Repd(i, n) Ford (i, (n) - 1, 0)
#define Fe(...) for (auto __VA_ARGS__)
template <class C> inline int isz(const C& c) { return static_cast<int>(c.size()); }
template <class T> inline bool chmin(T& a, const T& b) { return (a > b) ? a = b, true : false; }
template <class T> inline bool chmax(T& a, const T& b) { return (a < b) ? a = b, true : false; }
constexpr ld eps = 1e-9;
constexpr int inf = 1e9;
constexpr ll linf = 1e18;
// =============================================================================
constexpr int maxn = 5e4 + 5;
constexpr int logn = 20;
constexpr int base = 31;
struct mint {
int v;
static constexpr int mod = 1e9 + 7;
mint() : v(0) {}
mint(ll _v) : v(int(_v % mod)) { v += (v < 0) * mod; }
mint& operator+=(const mint& o) {
if ((v += o.v) >= mod) v -= mod;
return *this;
}
mint& operator-=(const mint& o) {
if ((v -= o.v) < 0) v += mod;
return *this;
}
mint& operator*=(const mint& o) {
return *this = mint(1LL * v * o.v);
}
friend mint operator+(const mint& a, const mint& b) {
return mint(a) += b;
}
friend mint operator-(const mint& a, const mint& b) {
return mint(a) -= b;
}
friend mint operator*(const mint& a, const mint& b) {
return mint(a) *= b;
}
friend bool operator==(const mint& a, const mint& b) {
return a.v == b.v;
}
friend bool operator!=(const mint& a, const mint& b) {
return a.v != b.v;
}
bool operator<(const mint& o) const {
return v < o.v;
}
};
int n;
char a[maxn];
vector<int> g[maxn];
mint power[maxn];
mint hdown[maxn], hup[maxn];
bool found;
bool rem[maxn];
int sz[maxn];
int up[maxn][logn];
int dep[maxn];
vector<int> node;
vector<pair<mint, int>> layer[maxn];
void getSz(int u, int p) {
sz[u] = 1;
Fe (v : g[u]) {
if (rem[v] || v == p) continue;
getSz(v, u);
sz[u] += sz[v];
}
}
int getCen(int target, int u, int p) {
Fe (v : g[u]) {
if (rem[v] || v == p) continue;
if (sz[v] * 2 > target) return getCen(target, v, u);
}
return u;
}
void prepare(int u, int p) {
node.push_back(u);
layer[dep[u]].emplace_back(hdown[u], u);
For (i, 1, logn - 1) {
up[u][i] = up[up[u][i - 1]][i - 1];
}
Fe (v : g[u]) {
if (rem[v] || v == p) continue;
up[v][0] = u;
dep[v] = dep[u] + 1;
hdown[v] = hdown[u] * base + (a[v] - 'a' + 1);
hup[v] = hup[u] + power[dep[v] - 1] * (a[v] - 'a' + 1);
prepare(v, u);
}
}
int lift(int u, int dist) {
Repd (i, logn) {
if (dist >> i & 1) u = up[u][i];
}
return u;
}
int getLca(int u, int v) {
if (dep[u] < dep[v]) swap(u, v);
int dist = dep[u] - dep[v];
u = lift(u, dist);
if (u == v) return u;
Repd (i, logn) {
if (up[u][i] != up[v][i]) {
u = up[u][i];
v = up[v][i];
}
}
return up[u][0];
}
mint getHash(int u, int v) {
return hdown[u] - hdown[up[v][0]] * power[dep[u] - dep[v] + 1];
}
void calc(int u, int len) {
if (found) return;
hdown[u] = a[u] - 'a' + 1;
hup[u] = a[u] - 'a' + 1;
node.clear();
up[u][0] = 0;
dep[u] = 1;
prepare(u, -1);
For (i, 1, n) {
sort(all(layer[i]));
}
Fe (A : node) {
if (found) break;
int odist = len - dep[A] + 1;
if (odist > dep[A] || odist < 1) continue;
const auto& cur = layer[odist];
int C = lift(A, odist - 1);
if (hdown[C] != hup[C]) continue;
mint ohash = getHash(A, C);
auto it = lower_bound(all(cur), pair(ohash, -1));
if (it == cur.end()) {
continue;
}
while (it != cur.end()) {
if (it->fi != ohash) break;
int B = it->se;
if (getLca(A, B) == u) {
found = true;
break;
} else {
++it;
}
}
}
For (i, 1, n) {
layer[i].clear();
}
}
void cd(int u, int len) {
if (found) return;
getSz(u, -1);
u = getCen(sz[u], u, -1);
rem[u] = true;
calc(u, len);
for (int v : g[u]) {
if (rem[v] == false) {
cd(v, len);
}
}
}
bool check(int len) {
found = false;
memset(rem, false, sizeof(rem));
cd(1, len);
return found;
}
signed main() {
cin >> n >> (a + 1);
Rep (_, n - 1) {
int u, v; cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
power[0] = 1;
For (i, 1, n) power[i] = power[i - 1] * base;
int l, r;
int ans = 0;
l = 0, r = n / 2;
while (l <= r) {
int m = (l + r) / 2;
if (check(2 * m + 1)) {
l = m + 1;
} else {
r = m - 1;
}
}
chmax(ans, 2 * r + 1);
l = 1, r = n / 2;
while (l <= r) {
int m = (l + r) / 2;
if (check(2 * m)) {
l = m + 1;
} else {
r = m - 1;
}
}
chmax(ans, 2 * r);
cout << ans << '\n';
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
7 ms |
3404 KB |
Output is correct |
| 2 |
Correct |
24 ms |
3516 KB |
Output is correct |
| 3 |
Correct |
82 ms |
3532 KB |
Output is correct |
| 4 |
Correct |
150 ms |
3660 KB |
Output is correct |
| 5 |
Correct |
2 ms |
3276 KB |
Output is correct |
| 6 |
Correct |
2 ms |
3276 KB |
Output is correct |
| 7 |
Correct |
3 ms |
3276 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
5074 ms |
11848 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
5091 ms |
11336 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
7 ms |
3404 KB |
Output is correct |
| 2 |
Correct |
24 ms |
3516 KB |
Output is correct |
| 3 |
Correct |
82 ms |
3532 KB |
Output is correct |
| 4 |
Correct |
150 ms |
3660 KB |
Output is correct |
| 5 |
Correct |
2 ms |
3276 KB |
Output is correct |
| 6 |
Correct |
2 ms |
3276 KB |
Output is correct |
| 7 |
Correct |
3 ms |
3276 KB |
Output is correct |
| 8 |
Execution timed out |
5074 ms |
11848 KB |
Time limit exceeded |
| 9 |
Halted |
0 ms |
0 KB |
- |
