题解中有很多建虚树的方法,例如:
void push_stk(int x){
if(topp==1) return (void)(stk[++topp]=x);
int lca=LCA(x,stk[topp]);
if(lca==stk[topp]) return;
while(topp>1&&dfn[stk[topp-1]]>=dfn[lca]) G[stk[topp-1]].push_back(stk[topp]),--topp;
if(stk[topp]!=lca) G[lca].push_back(stk[topp]),stk[topp]=lca;
stk[++topp]=x;
}
但是这样建成的虚树,可能不会包含所有关键节点,
如本题的第二个询问:关键节点为 5 7 8 3。
但以上面的写法,建出来的虚树节点只有 1 5 3。
为什么虚树没有建完全,却能A呢?是本题的特性吗?