求好心人帮忙下个数据
  • 板块灌水区
  • 楼主Chinshyo
  • 当前回复4
  • 已保存回复4
  • 发布时间2023/8/12 18:50
  • 上次更新2023/11/3 04:14:10
查看原帖
求好心人帮忙下个数据
312820
Chinshyo楼主2023/8/12 18:50

以下是这道题的代码

调了好长时间了,过不去这个点。求好心人提交这个代码到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; 
}
2023/8/12 18:50
加载中...