关于题解虚树求法的正确性？

题解中有很多建虚树的方法，例如：

CPP

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呢？是本题的特性吗？

关于题解虚树求法的正确性？

讨论操作

回复

相关推荐

关于题解虚树求法的正确性？