#include #include #include #include #include #include using namespace std; namespace IO { const int BUFSIZE = 1 << 20; char ibuf[BUFSIZE], *is = ibuf, *it = ibuf; inline char gc() { if (is == it) it = (is = ibuf) + fread(ibuf, 1, BUFSIZE, stdin); return *is++; } } inline int gi() { register int data = 0, w = 1; register char ch = 0; while (ch != '-' && (ch > '9' || ch < '0')) ch = IO::gc(); if (ch == '-') w = -1 , ch = IO::gc(); while (ch >= '0' && ch <= '9') data = data * 10 + (ch ^ 48), ch = IO::gc(); return w * data; } #define MAX_N 1000005 struct Node { int ch[2], fa, size, v; } t[MAX_N]; inline int get(int x) { return t[t[x].fa].ch[1] == x; } typedef unsigned long long ull; const ull base = 100007; ull pw[MAX_N << 1]; ull hs1[2][MAX_N << 1], hs2[2][MAX_N << 1]; ull getHash(ull *hs, int l, int r) { return hs[r] - hs[l - 1] * pw[r - l + 1]; } int N, L[MAX_N], R[MAX_N], rL[MAX_N], rR[MAX_N], P[MAX_N << 1], cnt; void dfs(int x) { P[L[x] = ++cnt] = x; if (t[x].ch[0]) dfs(t[x].ch[0]); if (t[x].ch[1]) dfs(t[x].ch[1]); P[R[x] = ++cnt] = x; t[x].size = t[t[x].ch[0]].size + t[t[x].ch[1]].size + 1; } void rdfs(int x) { P[rL[x] = ++cnt] = x; if (t[x].ch[1]) rdfs(t[x].ch[1]); if (t[x].ch[0]) rdfs(t[x].ch[0]); P[rR[x] = ++cnt] = x; } int main () { N = gi(); pw[0] = 1; for (int i = 1; i <= 2 * N; i++) pw[i] = pw[i - 1] * base; for (int i = 1; i <= N; i++) t[i].v = gi(); for (int x = 1; x <= N; x++) { int ls = gi(), rs = gi(); if (ls != -1) t[x].ch[0] = ls, t[ls].fa = x; if (rs != -1) t[x].ch[1] = rs, t[rs].fa = x; } dfs(1); for (int i = 1; i <= cnt; i++) hs1[0][i] = hs1[0][i - 1] * base + t[P[i]].v; for (int i = 1; i <= cnt; i++) hs2[0][i] = hs2[0][i - 1] * base + get(P[i]); cnt = 0; rdfs(1); for (int i = 1; i <= cnt; i++) hs1[1][i] = hs1[1][i - 1] * base + t[P[i]].v; for (int i = 1; i <= cnt; i++) hs2[1][i] = hs2[1][i - 1] * base + (get(P[i]) ^ 1); int ans = 1; for (int x = 1; x <= N; x++) { int ls = t[x].ch[0], rs = t[x].ch[1]; if (t[ls].size != t[rs].size) continue; if (getHash(hs1[0], L[ls], R[ls]) != getHash(hs1[1], rL[rs], rR[rs])) continue; if (getHash(hs2[0], L[ls], R[ls]) != getHash(hs2[1], rL[rs], rR[rs])) continue; ans = max(ans, t[x].size); } printf("%d\n", ans); return 0; }

题库

题库

3519.[NOIP2018 普及组] 对称二叉树

提交记录

测试用例