CSP2023-12树上搜索题解

刚考完csp，这道题是大模拟题，题意不难理解。以下是题目链接：

http://118.190.20.162/view.page?gpid=T178

当时考场上这道题调了好久没调出来，忽略了很多细节。在这里分享一下满分题解及思路，帮大家避避坑。

#include <iostream>
#include<stdio.h>
#include<queue>
#include<cstring>
#include<string>
#include <map>
#include<cmath>
#include<cstring>
#include<algorithm>
#include <vector>
#include <unordered_set>
#include <unordered_map>
#define MAX 0x3f3f3f3f3f3f  //注意这个数要开大一点，不然会溢出
using namespace std;
typedef long long LL;

LL n, m;
// 定义结构体记录每个点的信息，包括其父节点，后代集合，以及其权重
struct point {
	int father;
	unordered_set<int> sons;
	LL weight;
} points[2010];
// 记录每个结点是否被去除
bool used[2010];
// 计算当前剩下的结点的总权重
LL calv(){
	LL sum = 0;
	for (int i = 1;i <= n;i++) {
		if (!used[i]) sum += points[i].weight;
	}
	return sum;
}
// 用于判断需要测试的点是否是提问点的后代
bool searchfa(int x,int fa) {
	if (x == 0) return false;
	if (fa == points[x].father || fa == x)	return true;
	else return searchfa(points[x].father,fa);
}
// 用于构建树
bool fillfa(unordered_set<int> x, int fa) {
	if (fa == 0) return false;
	unordered_set<int>::iterator it;
	for (it = x.begin();it != x.end();it++) {
		points[fa].sons.insert(*it);
	}	
	fillfa(x,points[fa].father);
}
// 用于初始化used数组
void fill(int x) {
	if(x==0)for (int i = 1;i <= n;i++) used[i]=false;
	else for (int i = 1;i <= n;i++) used[i] = true;
}
int main() {
	// 输入部分
	cin >> n >> m;
	for (int i = 1;i <= n;i++) {
		cin >> points[i].weight;
	}
	points[1].father = 0;
	for (int i = 2;i <= n;i++) {
		int a;
		cin >> a;
		points[i].father = a;
		points[i].sons.insert(i);
		fillfa(points[i].sons,a);
		points[i].sons.erase(i);
	}
	// 先求出提问结点，根据测试点是否是其后代分为两类处理
	for (int i = 1;i <= m;i++) {
		LL target;
		LL remain = n;
		fill(0);
		cin >> target;
		// remain记录当前剩余节点数量，为1退出
		while (remain != 1) {
			LL sum = calv();
			int index = 0;
			LL w = MAX;
			// 求出提问结点index
			for (int i = 1;i <= n;i++) {
				if(!used[i]) {
					unordered_set<int>::iterator it;
					LL sum1 = points[i].weight;
					for (it = points[i].sons.begin();it != points[i].sons.end();it++) {
						if(!used[*it])
							sum1 += points[*it].weight;;
					}
					if (abs(sum - 2 * sum1) < w) {
						w = abs(sum - 2 * sum1);
						index = i;
					}
				}
			}
			cout << index << " ";
			// 根据测试点是否是其后代分为两类处理,是后代保留测试点子树
			if(searchfa(target,index)){
				for (int i = 1;i <= n;i++) {
					if(!points[index].sons.count(i))
						used[i] = true;
				}
				used[index] = false;
				remain = 1;
				unordered_set<int>::iterator it;
				for (it = points[index].sons.begin();it != points[index].sons.end();it++) {
					if(!used[*it])
						remain += 1;
				}
			}
			// 不是后代则去除测试点子树
			else{
				used[index] = true;
				remain -= 1;
				unordered_set<int>::iterator it;
				for (it = points[index].sons.begin();it != points[index].sons.end();it++) {
					
					if(!used[*it])remain -= 1;
					used[*it] = true;
				}
			}
		}
		cout << endl;

	}
	return 0;
}