在使用单调栈方法建立 虚树 的时候什么时候可以使用 k 数组的第一个节点作为第一个入栈元素而不使用 1 号节点啊?
直接使用 k1 号节点:
sort(k+1,k+m+1,cmp);
tot=top=head[1]=0;
st[++top]=1;
for(int i=1;i<=m;i++){
if(k[i]==1)
continue;
int l=Lca(k[i],st[top]);
if(l!=st[top]){
while(top>2&&deep[st[top-1]]>deep[l]){
add(st[top-1],st[top]);
top--;
}
if(st[top-1]!=l){
head[l]=0;
add(l,st[top]);
st[top]=l;
}
else{
add(st[top-1],st[top]);
top--;
}
}
head[k[i]]=0;
st[++top]=k[i];
}
for(int i=2;i<=top;i++)
add(st[i-1],st[i]);
此时若 k 序列里的元素为 :2 3 4 ,具体树形态如下图中图 1 ,我会错误的建出如下的图 2,求问应该如何改正?
图一:

图二:
