「Prufer 序列」

_Fontainebleau_ · 2021-12-07 22:06:29 · 个人记录

前言

icpc 上考到了板子题。然后找规律做出来了。

正文

Prufer 序列可以将一个带标号 n 个结点的树用 [1,n] 中的 n-2 个整数表示。你也可以把它理解为完全图的生成树与数列之间的双射。—— OI-wiki

怎么建立 Prufer 序列呢？

每次选择编号最小的叶子点删除，并在序列中记录其父亲。重复 n-2 次后只剩 2 个节点，结束。

线性求 Prufer 序列

维护一个指针 p，使其指向最小的叶子点。每次删除时操作如下：

• 删除 p 对应的节点，检查是否出现新叶子节点（即其父亲 x 是否变成叶子节点）。
• 如果产生新叶子节点，则比较 x,p 的大小。如果 x>p 那么不管他，迟早会被扫到。如果 x<p 那么立即删除。
• 向后移动指针，直到下一个叶子节点。

for(int i=1,j=1;i<=n-2;i++,j++)
{
    while(d[j]) ++j;p[i]=f[j];
    while(i<=n-2&&!--d[p[i]]&&p[i]<j)   p[i+1]=f[p[i]],++i;
}

线性建树

极其类似上文。

p[n-1]=n;
for(int i=1,j=1;i<n;i++,j++)
{
    while(d[j]) ++j;f[j]=p[i];
    while(i<n&&!--d[p[i]]&&p[i]<j)  f[p[i]]=p[i+1],++i;
}

一些式子

• $$n^{n-2}$$

CF156D Clues

sol.