2023.10.29晚，在随机做AtCoder的时候见到了[ABC303Ex] Constrained Tree Degree。然后开始思考DP，未果后看题解，发现是 Prufer 序列 -> 尝试学习 Prufer 序列。
什么是 Prufer序列
Prufer序列是一种将带标号的树用一个唯一的整数序列表示的方法，是解决树计数问题的工具。
给一棵有根树，这里给出转化为 Prufer 序列的方式。
重复以下操作直到树只剩下两个点：
- 找到一个度数为 \(1\) 且编号最小的点。
- 将其父亲节点的编号加入序列中，并删除这个节点。
操作结束后就得到了 Prufer 序列。其中第一步中找到编号最小的点即保证了树转化为 Prufer 序列的唯一性，同时也方便把 Prufer 序列转化为无根树。
剩下的明天写。
标签：笔记,转化,根树,编号,序列,Prufer,节点 From： https://www.cnblogs.com/AzusidNya/p/17796645.html