线形时间由prufer序列重构树

yangff的由树得到prufer序列(手动斜眼笑)
考虑重构树怎么搞……

这种代码的话,直接贴上来就好了呀 ——主席

所以直接上代码恩
对于得到的prufer 序列P[],重构树,我们可以这样搞:
求出对于后缀[i,..,n-2]最小的没有出现的数的大小,存在一个数组中,不妨设为A[]
然后每次取当前标号最小的叶子节点接上当前序列开头……就这样了

int A[N],P[N],isleaf[N],now_leaf;
get_A();
get_isleaf();
now_leaf=A[1];
for(int i=1;i<=n-2;i++)
{
    fa[P[i]]=now_leaf;
  deg[P[i]]--;
  if(deg[P[i]]=1)isleaf[P[i]]=1;
  if(i==n-2)break;
  \\得到下一个标号最小的叶子节点……下一叶子节点u一定满足:
  \\isleaf[u]==1
  \\且A[i+1]<=u
  now_leaf=A[i+1];
  while(!isleaf[now_leaf]&&now_leaf<n)now_leaf++;
 }
 Get_rest_two_link();

Comments

comments powered by Disqus