关于题解虚树求法的正确性?
查看原帖
关于题解虚树求法的正确性?
398980
Bai_Kking楼主2023/10/11 21:19

题解中有很多建虚树的方法,例如:

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 35\ 7\ 8\ 3。

但以上面的写法,建出来的虚树节点只有 1 5 31\ 5\ 3。

为什么虚树没有建完全,却能A呢?是本题的特性吗?

2023/10/11 21:19
加载中...