今天我们来看CSP202312C.树上搜索这道题目题意分析本题要求模拟一个基于二分策略的分类提问过程。给定一棵以 1 为根的树每个节点代表一个类别并带有一个权重。对于每个查询给定的目标类别target需要按照以下规则生成提问序列维护一个候选类别集合初始包含全部 n 个类别总权重为所有类别的权重之和。对于候选集合中的每个类别u计算其子树在候选集合中的权重和sum[u]并计算delta |sum[u] - (total - sum[u])|即该类别子树权重与其余部分权重之差的绝对值。选择delta最小的类别作为本次提问类别若并列取编号较小者输出该编号。判断目标类别target是否在该类别的子树内根据原始树的祖先关系若在则候选集合缩小为该类别及其后代删除其余节点若不在则删除该类别及其后代保留其余节点。重复步骤 2-4直到候选集合中只剩一个类别停止。需要输出每次提问的类别编号。思路本题数据范围n ≤ 2000m ≤ 100允许 O(n²) 级别的查询模拟。预处理读入权重、父子关系建树。进行一次 DFS得到每个节点的 DFS 序区间[tin, tout]用于 O(1) 判断节点之间的祖先关系同时计算每棵子树的原始权重和subSum[u]。模拟一次查询使用数组sumClosure[u]表示当前候选集合中以u为根的子树内仅限仍在候选集合中的节点的权重和。初始时等于subSum[u]。维护变量total表示当前候选集合的总权重初始为subSum[1]。候选集合用vectorint cand存储所有还在候选中的类别编号。循环直到cand.size() 1遍历cand中每个节点u计算delta abs(2 * sumClosure[u] - total)选出最优提问节点best。将best加入答案数组。判断target是否在best的子树中利用 DFS 序inSubtree(best, target)返回tin[best] tin[target] tout[target] tout[best]。根据回答缩小候选集合若回答“是”保留best及其后代对于当前cand中每个节点v若v不在best子树内则删除。若回答“否”删除best及其后代若v在best子树内则删除。删除节点时需要更新total和sumClosuretotal - w[v]对于v的所有祖先沿着父指针向上直到根将它们的sumClosure减去w[v]因为这些祖先的“候选子树和”不再包含被删除的节点。更新候选集合cand为保留的节点。注意由于删除节点时更新祖先的sumClosure下一轮计算中sumClosure[u]即为当前候选集合中u子树内的权重和符合题意。时间复杂度每个查询最多进行 n-1 次提问每次扫描候选集合 O(n)并更新被删除节点的祖先 O(depth)最坏 O(n²)。对于 n≤2000m≤100总时间在可接受范围内。代码#includebits/stdc.husingnamespacestd;intmain(){ios::sync_with_stdio(false);cin.tie(0);intn,m;cinnm;vectorlonglongw(n1);for(inti1;in;i)cinw[i];vectorintparent(n1,0);vectorvectorintchildren(n1);for(inti2;in;i){cinparent[i];children[parent[i]].push_back(i);}// DFS 序用于判断祖先关系vectorinttin(n1),tout(n1);vectorlonglongsubSum(n1,0);inttimer0;functionvoid(int)dfs[](intu){tin[u]timer;subSum[u]w[u];for(intv:children[u]){dfs(v);subSum[u]subSum[v];}tout[u]timer;};if(n1)dfs(1);autoinSubtree[](intu,intv){returntin[u]tin[v]tout[v]tout[u];};for(intq0;qm;q){inttarget;cintarget;vectorlonglongsumClosuresubSum;longlongtotalsubSum[1];vectorintcand;cand.reserve(n);for(inti1;in;i)cand.push_back(i);vectorintans;ans.reserve(n);while(cand.size()1){intbest-1;longlongbestDeltaLLONG_MAX;// 选择 wδ 最小的类别for(intu:cand){longlongdelta2*sumClosure[u]-total;if(delta0)delta-delta;if(deltabestDelta||(deltabestDeltaubest)){bestDeltadelta;bestu;}}ans.push_back(best);// 判断目标类别是否在 best 的子树中boolanswerYesinSubtree(best,target);vectorintnewCand;newCand.reserve(cand.size());for(intv:cand){boolkeep;if(answerYes){keepinSubtree(best,v);}else{keep!inSubtree(best,v);}if(keep){newCand.push_back(v);}else{// 删除节点 v更新 total 和所有祖先的 sumClosuretotal-w[v];intuv;while(u!0){sumClosure[u]-w[v];uparent[u];}}}cand.swap(newCand);}for(size_t i0;ians.size();i){if(i)cout ;coutans[i];}cout\n;}return0;}总结本题核心在于理解二分提问的决策过程并高效维护动态变化的候选集合及其子树权重和。通过 DFS 序快速判断祖先关系利用父指针链更新权重避免了重复计算使得单次查询的复杂度可以接受。代码实现时需注意数据范围使用long long防止溢出以及并列时选择编号较小的类别。