基本信息
定义：prufer序列是无根树和序列的双向映射，并且描述了节点读书以及父节点的信息。
使用场景：将构造树的问题转化为构造序列，将统计树的问题转化为统计序列，将树的dp转化为序列的dp。
如何得到prufer序列？
-
统计树上的所有节点的度数 \(d_i\) 。
-
找到所有度数为 \(1\) 的节点中编号最小的节点 \(cur\) 。
-
prufer 序列的第 \(i\) 项 \(p_i=fa[cur]\) ，同时将 \(d_{fa[cur]}\) 减一。
-
重复 \(2,3\) 直到剩余两个节点。