有没有大佬能告诉我D题哪里错了

写的头昏脑花的,自己写了几个案例都过了,但不知道错哪了,求教。

#include <bits/stdc++.h>
using namespace std;

struct NODE {
	int cnt_son;
	int son[2005];
	int father;
	long long int energy;
} parent[200005];

int main() {
	int n,  sum1 = 0, maxi = 1, f = 0, a, b[100005] = {0};
    long long int res=0;
	cin >> n;
	for (int i = 0; i < n - 1; i++) {
		cin >> a;
		parent[i + 2].father = a;
		parent[a].cnt_son++;
		parent[a].son[parent[a].cnt_son] = i + 2;
	}
	for (int i = 0; i < n; i++) {
		cin >> b[i];
		sum1 += b[i];
	}
	sort(b, b + n);
	for (int i = 1; i <= n; i++) {
		if (parent[maxi].cnt_son < parent[i].cnt_son)
			maxi = i;
	}
	for (int k = parent[maxi].cnt_son; k >= 0 ; k--) {
		for (int i = 1; i <= n; i++) {
			if (parent[i].cnt_son == k) {
				parent[i].energy = b[f];
				f++;
			}
		}
	}
	for (int k = 0; k <= parent[maxi].cnt_son ; k++) {
		for (int i = 1; i <= n; i++) {
			if (parent[i].cnt_son == k) {
				parent[parent[i].father].energy += parent[i].energy;

			}
		}
	}
	for (int i = 1; i <= n; i++) {
		res+=parent[i].energy;	
	}
	cout<<res;
}

全部评论
第一眼看到son的大小和b的大小都不对,这题n是2e5的,别的错不知道有没有
点赞 回复
分享
发布于 2023-01-18 21:51 北京
不懂你思路,但是这里提供一组hack数据 6 1 2 3 4 1 3 2 7 7 6 3 我的答案:95 选择能量为 7 的球,放在节点 5 上,获得能量 7 选择能量为 7 的球,放在节点 4 上,获得能量 14 选择能量为 6 的球,放在节点 3 上,获得能量 20 选择能量为 3 的球,放在节点 2 上,获得能量 23 选择能量为 3 的球,放在节点 6 上,获得能量 3 选择能量为 2 的球,放在节点 1 上,获得能量 28 总共95 你的代码输出61,没有95优 另外,看你结构体NODE中的son[]开到了2000,2000*200000的内存一般会超的,而且这题可能有节点的孩子数超过2000,数组又显得小了 建议学学链式前向星或者vector建图,可以解决上述问题
点赞 回复
分享
发布于 2023-01-18 22:01 湖南
联易融
校招火热招聘中
官网直投
牛牛
点赞 回复
分享
发布于 2023-01-30 17:42 未知

相关推荐

1 收藏 评论
分享
牛客网
牛客企业服务