pop 之后配对要重新导向堆顶,特判只有一个儿子的情况:
int EraseNode(int root) {
static std::queue<int> node_list;
for(int x:node_[root].son_) {
node_list.push(x);
node_[x].fa_=-1;
node_[x].top_=x;
}
node_[root].son_.clear();
int x(0),y(0),z(0);
while(node_list.size()>1u) {
x=node_list.front();
node_list.pop();
y=node_list.front();
node_list.pop();
node_[root].top_=z=MergeId(x,y);
node_list.push(z);
}
if(!node_list.empty()) {
node_[root].top_=node_list.front();
node_list.pop();
}
return node_[root].top_;
}
删去最后的 if 中第一句对 top_ 的赋值会导致 WA on Sub1# 6-12,Sub2# 1。