关于虚树
  • 板块学术版
  • 楼主xxmb
  • 当前回复22
  • 已保存回复22
  • 发布时间2024/11/18 09:53
  • 上次更新2024/11/18 14:50:47
查看原帖
关于虚树
818000
xxmb楼主2024/11/18 09:53

在使用单调栈方法建立 虚树 的时候什么时候可以使用 kk 数组的第一个节点作为第一个入栈元素而不使用 11 号节点啊?

直接使用 k1k_1 号节点:

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]);

此时若 kk 序列里的元素为 :2 3 4 ,具体树形态如下图中图 11 ,我会错误的建出如下的图 22,求问应该如何改正?

图一:

图二:

2024/11/18 09:53
加载中...