Prufer序列 入门 — P2290 [HNOI2004]树的计数

0 前置知识点

1 Prufer 序列

对于一个带编号的无根树,其 Prufer 序列按以下过程处理

  1. 选取所有节点中度数最小编号最小的一个节点
  2. 输出其相邻的编号
  3. 回到 1 ,直到只剩两个节点为止

每个 Prufer 序列,都对应唯一的一个带编号的无根树

Continue reading “Prufer序列 入门 — P2290 [HNOI2004]树的计数”

Luogu P2607 [ZJOI2008]骑士

题目链接: https://www.luogu.org/problemnew/show/P2607

题目意思非常简单,给你一张图,然后图中不能选最大相邻点,最后最大的选中的点的权值

很容易想到 没有上司的舞会 这种树形 DP 题目,但是显然,这,并不是一棵树

根据题目可得,每一个人只会有一条出边,即,这张图中,一张节点个数为 $n$ 的联通块,会有 $n$ 条边

环套树没得跑了

即每一个联通块中一定有一条边,删掉后就是树了

设这条边为 $u – v$ 的边,则 $\max(f_{u,0}, f_{u,1})$ 就是这个联通块的答案

建双向边判环即可

至于代码中的 xor ,当反向边即可

Continue reading “Luogu P2607 [ZJOI2008]骑士”