ccf认证 202312-3

小 C 观察了事先收集到的数据，并加以统计，得到了一个名词属于各个类别的可能性大小的信息。具体而言，每个类别都可以赋予一个被称为权重的值，值越大，说明一个名词属于该类别的可能性越大。由于每次向用户的询问可以获得两种回答，小 C 联想到了二分策略。他设计的策略如下：

1. 对于每一个类别，统计它和其全部后代类别的权重之和，同时统计其余全部类别的权重之和，并求二者差值的绝对值，计为 𝑤𝛿；
2. 选择 𝑤𝛿 最小的类别，如果有多个，则选取编号最小的那一个，向用户询问名词是否属于该类别；
3. 如果用户回答“是”，则仅保留该类别及其后代类别，否则仅保留其余类别；
4. 重复步骤 1，直到只剩下一个类别，此时即可确定名词的类别。

小 C 请你帮忙编写一个程序，来测试这个策略的有效性。你的程序首先读取到所有的类别及其上级次级关系，以及每个类别的权重。你的程序需要测试对于被归类到给定类别的名词，按照上述策略提问，向用户提出的所有问题。

思路：树的删除操作，暴力能过。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
vector<int>t[2010];
int a[2010];
int w[2010];
int vis[2010];
int sum;
int n,m;
int dfs(int u){
	if(vis[u])return 0;
	w[u]=a[u];
	for(int i=0;i<t[u].size();i++)
	w[u]+=dfs(t[u][i]);
	return w[u];
}
int dfs1(int q,int x){
	if(vis[x])return 0;
	if(q==x)return 1;
	for(int i=0;i<t[x].size();i++)
	if(dfs1(q,t[x][i]))return 1;
	return 0;
}
void run(int q,int root){
	int cnt=0;
	int flag1;
	int sum=w[root];
	int flag2;
	for(int i=n;i>=1;i--)if(w[i]){
		cnt++;
		flag1=abs(2*w[i]-sum);
		flag2=i;
	}
	if(cnt==1)return ;
	for(int i=1;i<=n;i++)
	if(w[i]&&abs(2*w[i]-sum)<flag1){
	flag1=abs(2*w[i]-sum);
	flag2=i;
	}
	cout<<flag2<<' ';
	if(!dfs1(q,flag2)){
		vis[flag2]=1;
		memset(w,0,sizeof(w));
		w[root]=dfs(root);
	}else {
		root=flag2;
		memset(w,0,sizeof(w));
		w[flag2]=dfs(flag2);
	}
	run(q,root);
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	cin>>a[i],sum+=a[i];
	for(int i=2;i<=n;i++)
	{
		int b;
		cin>>b;
		t[b].push_back(i);
	}
	while(m--){
		int q;
		memset(vis,0,sizeof(vis));
		memset(w,0,sizeof(w));
		w[1]=dfs(1);
		cin>>q;
		run(q,1);
		cout<<endl;
	}
	return 0;
}