树上搜索
计算机软件能力认证考试系统
第一次做，感觉特别复杂，要考虑很多情况。特别是如何删除树枝、如何保留新的树，都是难点。最后看了CCF-CSP认证考试 202312-3 树上搜索（不用struct建树、超短代码！这篇，将自己的理解写在了下面。
本来我一开始想使用的是BFS遍历树，但是书写起来显然没有DFS轻便。我们对树的表示都是差不多的，都是使用了一个数组来记录每一个节点的子节点，方便从上往下遍历。
但是我缺乏的地方，或者说在本题最大是收获就是对book的妙用、set判断节点位置。
首先谈谈book的妙用吧。本来我以为book只能用来标记两种状态，be or not be（doge）。但是这题让我大开眼界。可以使用book[ cur ]++区分不同状态下的树，这极大方便了我们最后计算和比较delta的时候。试想，如果不能用book区分树，我们会老老实实对树进行修剪，遍历的时候也会老老实实从树根开始，这样太麻烦了。
其次是判断节点位置。这里使用了set将goal的所有父结点都加上去了。我一开始还没反应过来，但是写到后面才知道，这样会极大方便我们确定获得的节点相对goal节点的位置。只要判断set中是否存在这个节点即可！如果存在，那就是其父节点！这让我想到并查集，但是并查集是一个一个连着的，需要一层一层往上调。
AC：
//树上搜索 ans
#include <iostream>
#include <vector>
#include <set>
#include <cmath>
using namespace std;
#define ll long long
const int N=2e3+2;int n,m;
int goal;
vector<int>w(N,0); //单个类别权重
vector<ll>mulw(N,0); //记录当前和后代的总权重
vector<int>fa(N,0); //上级
vector<vector<int>>son(N); //子类
vector<int>book(N,0); //记录哪些节点被删除了 ll dfs(int cur)
{mulw[cur]=w[cur];book[cur]++; //我觉得这里才是点睛之笔！此处之所以是++，而不是=1，有大学问的//book的标记有两个作用，第一就是下面的删除类，第二就是main函数中用来区分不同的树！//比如，我们每次遍历新的树，此时根=2，book值为3，那么其子树的book值也为3。//当我们进行删除操作后，新树根=3，book值为4，子树的book值也为4。//那么那些book值为3的节点，就不在这棵树上了！ for(int i=0;i<son[cur].size();i++){int nex=son[cur][i];if(book[nex]==-1) continue; //被标记过的，跳过mulw[cur]+=dfs(nex); //否则当前总权重为后代权重相加 }return mulw[cur];
}int main()
{cin>>n>>m;for(int i=1;i<=n;i++){cin>>w[i];}for(int i=2;i<=n;i++){cin>>fa[i];son[fa[i]].push_back(i);}while(m--){cin>>goal; //待检测目标//每次检测都要更新一下book.assign(n+1,0); int curRoot=1; //当前root int cutNum=son[goal].size(); //goal的子节点个数 set<int>belongTo;for(int cur=goal;cur!=0;cur=fa[cur]) //将goal的上级全部装入set中 belongTo.insert(cur); //set之后用来判断goal是否为询问类型的后代 while(cutNum!=0 || curRoot!=goal) {//最后是只剩一个，退出循环。所以要满足curRoot指向goal，且goal变成叶子节点，没有后代 dfs(curRoot); //dfs的做用是计算当前树的所有类的权值 //获取到权值之后就相减，但是怎么减呢？有两点需要把握：//1.根类的权值就是总权值。我们只需要将根类的权值和子类的权值进行计算即可//2.我们用book的值来区分最新的树的节点，仔细看看下面的操作：vector<ll>delta(n+1); //差值存放 for(int i=1;i<=n;i++) //这里还没有区分树 delta[i]=abs(mulw[i]-(mulw[curRoot]-mulw[i])); //此类权重-剩余权重int askItem=curRoot; //将要询问的类，先默认设置为curRoot for(int i=1;i<=n;i++)if(book[curRoot]==book[i] && delta[i]<delta[askItem]) //book[curRoot]==book[i]将不是当前树的节点排除 askItem=i; cout<<askItem<<" ";//askItem有2种情况：1.为goal的父，2.为goal或者其子 if(belongTo.count(askItem)) //如果askItem是goal的父节点curRoot=askItem; //更新根else book[askItem]=-1; //否则标记，遍历树的时候将其删除 if(fa[askItem]==goal) //如果是其子，那删除的时候，就要记录goal剩下的子节点个数cutNum--; } cout<<endl;}return 0;
}
