#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7; // pe constante e mai rapid??
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int random(int st, int dr)
{
uniform_int_distribution<mt19937::result_type> gen(st, dr);
return gen(rng);
}
struct lampice
{
int n;
vector<vector<int>> g;
vector<char> colors;
vector<bool> seen;
vector<int> sz;
vector<int> depth;
vector<int> hashup;
vector<int> hashdown;
vector<int> power;
vector<vector<int>> rmq;
const int bsize = 15;
void init(int _n)
{
n = _n;
g = vector<vector<int>>(n + 1);
colors = vector<char>(n + 1);
seen = vector<bool>(n + 1);
sz = depth = hashup = hashdown = power = vector<int>(n + 1);
rmq = vector<vector<int>>(n + 1, vector<int>(bsize + 1));
}
void set_color(int pos, char x)
{
colors[pos] = x;
}
void add_edge(int a, int b)
{
g[a].push_back(b);
g[b].push_back(a);
}
void dfs_size(int node, int parent)
{
sz[node] = 1;
for (auto i : g[node])
{
if (i != parent && !seen[i])
{
dfs_size(i, node);
sz[node] += sz[i];
}
}
}
int find_centroid(int node, int parent, int size)
{
for (auto i : g[node])
{
if (i != parent && !seen[i] && sz[i] > size / 2)
{
return find_centroid(i, node, size);
}
}
return node;
}
void build_hashes(int node)
{
int base = random(2, 60);
int max_depth = 0;
function<void(int, int, int)> dfs_init = [&](int node, int parent, int d)
{
rmq[node][0] = parent;
for (int i = 1; i <= bsize && (1 << i) <= d; ++i)
{
rmq[node][i] = rmq[rmq[node][i - 1]][i - 1];
}
depth[node] = d;
max_depth = max(max_depth, d);
for (auto i : g[node])
{
if (i != parent && !seen[i])
{
dfs_init(i, node, d + 1);
}
}
};
dfs_init(node, 0, 0);
power[0] = 1;
for (int i = 1; i <= max_depth; ++i)
{
power[i] = (1ll * power[i - 1] * base) % mod;
}
function<void(int, int)> compute_hash = [&](int node, int parent)
{
hashup[node] = ((1ll * base * hashup[parent]) % mod + (colors[node] - 'a' + 1)) % mod;
hashdown[node] = (hashdown[parent] + (1ll * power[depth[node]] * (colors[node] - 'a' + 1)) % mod) % mod;
for (auto i : g[node])
{
if (i != parent && !seen[i])
{
compute_hash(i, node);
}
}
};
compute_hash(node, 0);
}
bool solve(int node, int k)
{
function<int(int, int)> get_hashup = [&](int a, int b)
{
int c = rmq[b][0];
return (hashup[a] - (1ll * hashup[c] * power[depth[a] - depth[c]]) % mod + mod) % mod;
};
function<int(int, int)> kth = [&](int node, int k)
{
int ans = node;
for (int i = bsize; i >= 0; --i)
{
if (k & (1 << i))
{
ans = rmq[ans][i];
}
}
return ans;
};
unordered_set<int> exista;
function<void(int, int, int)> add_subtree = [&](int node, int parent, int root)
{
exista.insert(get_hashup(node, root));
for (auto i : g[node])
{
if (i != parent && !seen[i])
{
add_subtree(i, node, root);
}
}
};
bool este = false;
function<void(int, int, int)> dfs = [&](int node, int parent, int d)
{
if (este)
{
return;
}
for (auto i : g[node])
{
if (i != parent && !seen[i])
{
dfs(i, node, d + 1);
}
}
int t = 2 * d - k;
int l = k - d;
if (t < 0 || l < 0)
{
return;
}
if (l == 0)
{
if (hashup[node] == hashdown[node])
{
este = true;
}
}
else
{
int qui = kth(node, l);
if (hashup[qui] == hashdown[qui] && exista.find(get_hashup(node, kth(node, l - 1))) != exista.end())
{
este = true;
}
}
};
for (auto i : g[node])
{
if (!seen[i])
{
dfs(i, node, 2);
if (este)
{
return este;
}
add_subtree(i, node, i);
}
}
return false;
}
bool decomp(int node, int k)
{
if (k > n)
{
return false;
}
dfs_size(node, 0);
node = find_centroid(node, 0, sz[node]);
build_hashes(node);
if (solve(node, k))
{
return true;
}
reverse(g[node].begin(), g[node].end());
if (solve(node, k))
{
return true;
}
reverse(g[node].begin(), g[node].end());
seen[node] = true;
for (auto i : g[node])
{
if (!seen[i])
{
if (decomp(i, k))
{
return true;
}
}
}
return false;
}
void reinit()
{
seen = vector<bool>(n + 1);
}
};
int32_t main()
{
cin.tie(nullptr)->sync_with_stdio(false);
int n;
cin >> n;
lampice g;
g.init(n);
for (int i = 1; i <= n; ++i)
{
char x;
cin >> x;
g.set_color(i, x);
}
for (int i = 1; i < n; ++i)
{
int u, v;
cin >> u >> v;
g.add_edge(u, v);
}
int ans = 1;
int st = 1, dr = n;
while (st <= dr)
{
int mid = (st + dr) / 2;
if (g.decomp(1, 2 * mid))
{
ans = max(ans, 2 * mid);
st = mid + 1;
}
else
{
dr = mid - 1;
}
g.reinit();
}
st = 1, dr = n;
while (st <= dr)
{
int mid = (st + dr) / 2;
if (g.decomp(1, 2 * mid + 1))
{
ans = max(ans, 2 * mid + 1);
st = mid + 1;
}
else
{
dr = mid - 1;
}
g.reinit();
}
cout << ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
340 KB |
Output is correct |
| 2 |
Correct |
17 ms |
484 KB |
Output is correct |
| 3 |
Correct |
71 ms |
596 KB |
Output is correct |
| 4 |
Correct |
85 ms |
744 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Correct |
0 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5062 ms |
13532 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5062 ms |
12752 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
340 KB |
Output is correct |
| 2 |
Correct |
17 ms |
484 KB |
Output is correct |
| 3 |
Correct |
71 ms |
596 KB |
Output is correct |
| 4 |
Correct |
85 ms |
744 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Correct |
0 ms |
212 KB |
Output is correct |
| 8 |
Execution timed out |
5062 ms |
13532 KB |
Time limit exceeded |
| 9 |
Halted |
0 ms |
0 KB |
- |
