@[XiaoYiii](/user/1025891) ~~换一个随机数据(滑稽)~~
by Y_QWQ_Y @ 2024-02-08 19:00:24
@[XiaoYiii](/user/1025891) 改了一下 $p$,过了。底数也要大一点捏。
```cpp
#include<bits/stdc++.h>
#include<time.h>
using namespace std;
const int N = 1e6 + 10;
const long long P = 100000000000000013, p = 1919810114514, P2 = 997080305606710007;
long long hash_l[N], hash_r[N], rr1, rr2, rr3, hl2[N], hr2[N];
int v[N], lc[N], rc[N], siz[N], n, ans;
void rd(){
mt19937 rnd(time(0));
scanf("%d", &n);
for(int i = 1; i <= n; i++) scanf("%d", &v[i]);
for(int i = 1; i <= n; i++) {scanf("%d%d", &lc[i], &rc[i]); lc[i] = max(0, lc[i]); rc[i] = max(0, rc[i]);}
rr1 = rnd() % p + 9894784;
rr2 = rnd() % p + 9999998;
rr3 = rnd() % p + 9999198;
}
void dfs(int u){
siz[u] = 1;
if(lc[u]) {dfs(lc[u]); siz[u] += siz[lc[u]];}
if(rc[u]) {dfs(rc[u]); siz[u] += siz[rc[u]];}
if(siz[lc[u]] == siz[rc[u]] && hash_l[lc[u]] == hash_r[rc[u]] && hl2[lc[u]] == hr2[rc[u]]) ans = max(ans, siz[u]);
hash_l[u] = (hash_l[lc[u]] * rr1 + v[u] * rr3 + hash_l[rc[u]] * rr2) % P;
hash_r[u] = (hash_r[rc[u]] * rr1 + v[u] * rr3 + hash_r[lc[u]] * rr2) % P;
hl2[u] = (hl2[lc[u]] * rr1 + v[u] * rr3 + hl2[rc[u]] * rr2) % P2;
hr2[u] = (hr2[rc[u]] * rr1 + v[u] * rr3 + hr2[lc[u]] * rr2) % P2;
return;
}
int main(){
rd();
hash_l[0] = 0;
hash_r[0] = 0;
dfs(1);
printf("%d\n", ans);
return 0;
}
```
by w9095 @ 2024-02-12 20:50:40