题解：P15386 Équinoxe / equinox

梦见云月 · 2026-10-26 15:13:22 · 题解

🐱

不敢笑，真是一边睡觉一边敲完的代码。

考虑贪心/dp，一般优先选择贪心。

考虑对于一个点，处理完了所有子节点后，当前度数是 d。

考虑如下情况：

• 父边不保留，此时保留两条子边显然最优。

• 父边保留，此时只能保留一条子边。

对于第二种情况，如果我们改成第一种情况，会有什么影响呢？

我们会发现父亲节点的度数变少了，也就是更容易达成 d\le 2 这个条件了，这是有利的，所以我们不会采取第二种方案。

这也是为什么我们一开始要考虑，处理完所有子节点后，最新的度数。

代码是好写的。