调了好长时间了,过不去这个点。求好心人提交这个代码到P5018里下载个数据,万分感谢!
#include<bits/stdc++.h>
#define ull unsigned long long
using namespace std;
const int N = 1000005, P1 = 131, P2 = 1331, P3 = 13331;
struct node {
int l, r, val;
} a[N];
int clh[N];
void dfs(int x, int pa) {
clh[x] = 0;
if(a[x].l == -1 && a[x].r == -1) {
clh[x] = 1;
return;
}
if(a[x].l != -1) {
dfs(a[x].l, x);
clh[x] += clh[a[x].l];
}
if(a[x].r != -1) {
dfs(a[x].r, x);
clh[x] += clh[a[x].r];
}
clh[x]++;
}
//bool check_list_l(int x) {
// if(a[x].l != -1) {
// if(a[x].r != -1) return false;
// return check_list_l(a[x].l);
// }
// return true;
//}
//
//bool check_list_r(int x) {
// if(a[x].r != -1) {
// if(a[x].l != -1) return false;
// return check_list_r(a[x].r);
// }
// return true;
//}
ull preo1(int x) {
// cout << x << endl;
if(a[x].l == -1 && a[x].r == -1) return a[x].val;
int res = 0;
if(a[x].l != -1) res += preo1(a[x].l) * P1;
if(a[x].r != -1) res += preo1(a[x].r) * P2;
return res + a[x].val * P3;
}
ull preo2(int x) {
// cout << x << endl;
if(a[x].l == -1 && a[x].r == -1) return a[x].val;
int res = 0;
if(a[x].r != -1) res += preo2(a[x].r) * P1;
if(a[x].l != -1) res += preo2(a[x].l) * P2;
return res + a[x].val * P3;
}
int main() {
int n;
cin >> n;
for(int i = 1; i <= n;i++) cin >> a[i].val;
for(int i = 1; i <= n; i++) cin >> a[i].l >> a[i].r;
int ans = INT_MIN;
dfs(1, -1);
//cout << "Hello" << endl;
// cout << preo1(2) << " " << preo2(6) << endl;
for(int i = 1; i <= n; i++) {
// if(a[i].l != -1 && a[i].r != -1) {
// cout << i << " : " <<
// }
// if(a[i].l != -1 && check_list_l(a[i].l)) {
// ans = max(ans, clh[i]);
// cout << " --- " << i << endl;
// }
// else if(a[i].r != -1 && check_list_r(a[i].r)) {
// ans = max(ans, clh[i]);
// cout << " --- " << i << endl;
// }
if(a[i].l != -1 && a[i].r != -1 && preo1(a[i].l) == preo2(a[i].r)) {
ans = max(ans, clh[i]);
}
}
if(ans == INT_MIN) ans = 1;
cout << ans << endl;
return 0;
}