#include <bits/stdc++.h>
#define ll long long
using namespace std;
typedef pair<int,int> pii;
const int maxn = 5e4 + 1;
const int LOG = 16;
const int base = 31;
const int modu = 1e9 + 7;
int n, pos[maxn], name[2*maxn], numNode, res = 0, timer1 = 0, timer = 0, RMQ[LOG+1][2*maxn], H[maxn], Lg[2*maxn]; ///LCA
char color[maxn];
int child[maxn], root = -1, node[maxn], sta[maxn], fin[maxn];
bool vis[maxn]; ///Centroid
int hashT[maxn], hashN[maxn], POW[maxn], inv_POW[maxn]; ///Hash
vector<int> adj[maxn], adjC[maxn];
#define MIN_HIGH(x,y) (H[name[x]] < H[name[y]] ? (x) : (y))
struct hashFunction
{
size_t operator()(const pair<int ,
int> &x) const
{
return x.first ^ x.second;
}
};
int add(int A, int B) {
ll tmp = A+B;
if (tmp >= modu) tmp -= modu;
if (tmp < 0) tmp += modu;
return tmp;
}
int mul(int A, int B) {
ll tmp = 1LL*A*B;
if (tmp >= modu) tmp %= modu;
return tmp;
}
void DFS_init(int u, int p) {
pos[u] = ++timer1;
name[timer1] = u;
for (int v: adj[u]) {
if (v == p) continue;
H[v] = H[u] + 1;
hashT[v] = add(color[v], mul(hashT[u],POW[1]));
hashN[v] = add(mul(color[v],POW[H[v]]),hashN[u]);
DFS_init(v,u);
name[++timer1] = u;
assert(timer1 <= 2*maxn);
}
}
int LCA(int u, int v) {
int l = pos[u], r = pos[v];
if (l > r) swap(l,r);
int k = Lg[r-l+1];
return name[MIN_HIGH(RMQ[k][l],RMQ[k][r - (1 << k) + 1])];
}
int binexpo(ll A, int b) {
int res = 1;
while (b) {
if (b & 1) res = 1LL*res*A%modu;
A = A*A % modu;
b >>= 1;
}
return res;
}
int inv(int A) {
return binexpo(A,modu-2);
}
int getHash(int u, int v, bool type) {
int L = LCA(u,v);
int hash_u = add(add(hashT[u], -mul(hashT[L],POW[H[u] - H[L]] )),mul(color[L],POW[H[u] - H[L]])), hash_v = add(hashN[v],-hashN[L]);
int target = H[u] - H[L];
if (H[L] <= target) hash_v = mul(hash_v,POW[target - H[L]]);
else hash_v = mul(hash_v,inv_POW[H[L] - target]);
if (type) hash_v = add(hash_v,-mul(color[v],POW[H[u] + H[v] - 2*H[L]]));
return add(hash_u,hash_v);
}
void DFS_size(int u, int p) {
child[u] = 1;
for (int v: adj[u]) {
if (v == p || vis[v]) continue;
DFS_size(v,u);
child[u] += child[v];
}
}
int get_centroid(int u, int p, int _n) {
for (int v: adj[u]) {
if (v == p || vis[v]) continue;
if (child[v] > _n/2) return get_centroid(v,u,_n);
}
return u;
}
void centroid_init(int u, int p) {
DFS_size(u,u);
int c = get_centroid(u,u,child[u]);
vis[c] = 1;
if (p != -1) adjC[p].push_back(c);
if (root == -1) root = c;
for (int v: adj[c]) {
if (vis[v]) continue;
centroid_init(v,c);
}
}
void DFS_centroid(int u) {
sta[u] = ++timer;
node[sta[u]] = u;
for (int v: adjC[u]) {
DFS_centroid(v);
}
fin[u] = timer;
}
void init() {
POW[0] = 1;
inv_POW[0] = 1;
for (int i = 1; i <= n; i++) {
POW[i] = mul(POW[i-1],base);
inv_POW[i] = inv(POW[i]);
}
hashT[1] = hashN[1] = color[1];
DFS_init(1,-1);
for (int i = 1; i <= timer1; i++) RMQ[0][i] = i;
for (int j = 1; j <= LOG; j++)
for (int i = 1; i <= timer1 - (1 << j)+1;i++)
RMQ[j][i] = MIN_HIGH(RMQ[j-1][i],RMQ[j-1][i + (1 << (j-1))]);
centroid_init(1,-1);
DFS_centroid(root);
}
bool curAns;
void DFS_ans(int u) {
vector<pii> tmp;
unordered_set<pii,hashFunction> st;
for (int v: adjC[u]) {
for (int i = sta[v]; i <= fin[v]; i++) {
int d = H[u] + H[node[i]] - 2*H[LCA(u,node[i])] + 1;
if (d == numNode) {
if (getHash(node[i],u,0) == getHash(u,node[i],0)) {
curAns = 1;
return;
}
} else if (d < numNode) {
int need = add(getHash(node[i],u,1),-mul(getHash(u,node[i],0),POW[numNode - d]));
if (st.find(pii(numNode - d + 1,need)) != st.end()) {
curAns = 1;
return;
}
tmp.emplace_back(pii(d,need));
}
}
if (v != adj[u].back())
for (int i = 0; i < tmp.size(); i++) st.insert(tmp[i]);
tmp.clear();
}
st.clear();
for (int v: adjC[u]) {
DFS_ans(v);
if (curAns) return;
}
}
bool getAns() {
curAns = 0;
DFS_ans(root);
return curAns;
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
freopen("Lampice.inp","r",stdin);
freopen("Lampice.out","w",stdout);
cin >> n;
Lg[0] = -1;
for (int i = 1; i <= 2*n; i++) Lg[i] = Lg[i/2] + 1;
for (int i = 1; i <= n; i++) {
char c;
cin >> c;
color[i] = c - 'a' + 1;
}
for (int i = 1; i < n; i++) {
int u,v;
cin >> u >> v;
adj[u].emplace_back(v);
adj[v].emplace_back(u);
}
init();
int L = 1, R = n/2, res = 1;
while (L <= R) {
int mid = (L + R)/2;
numNode = 2*mid;
if (getAns()) {
res =max(res,2*mid);
L = mid+1;
} else R = mid-1;
}
L = (res-1)/2; R = (n-1)/2;
while (L <= R) {
int mid = (L + R)/2;
numNode = 2*mid + 1;
if (getAns()) {
res = max(res,2*mid+1);
L = mid+1;
} else R = mid-1;
}
cout << res;
return 0;
}
Compilation message
lampice.cpp: In function 'void DFS_ans(int)':
lampice.cpp:163:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
163 | for (int i = 0; i < tmp.size(); i++) st.insert(tmp[i]);
| ~~^~~~~~~~~~~~
lampice.cpp: In function 'int main()':
lampice.cpp:182:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
182 | freopen("Lampice.inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
lampice.cpp:183:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
183 | freopen("Lampice.out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
2772 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
2772 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
2772 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
2772 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
