Mousetrap

前言 模拟赛之后被胁迫上去讲这题，没怎么准备，然后就在几个省的 OIer 面前当小丑。。倒是把我自己讲得很明白，但感觉对其他人不是很负责任，就来赎罪一下。。 更好的阅读体验。 题意 题目链接。 分析 以 \(t\) 为根，我们的目的是让老鼠走到根的操作数最小。 观察老鼠的动向，显然老鼠只要一往下走， ......

[CEOI2017] Mousetrap 策略其实比较好想但是把式子列出来有点难。 不妨把陷阱房作为根,这样就只用把老鼠往上赶。 设起始房为 st,陷阱房为 ed。 考虑 st 是 ed 的子节点,老鼠不可能送死所以会往子节点走,而管理员的最优策略是老鼠边走边堵。 直到老鼠动不了时,设在节点 x,把 ......

100黑祭。 首先以终点为根。 先考虑简单一点的情况：如果起点终点相邻，那么方案一定是让老鼠先走到一个叶子节点，然后断掉该节点到根路径上其它的分支。于是我们令 $f_i$ 表示从 $i$ 开始走到 $i$ 子树里的一个叶节点再返回所需的最小代价，每次dp从儿子里的次大值转移即可。 考虑不相邻的情况， ......