3161专题

GDOI Training #3161 灵异事件 树形dp+分类讨论

题目链接:传送门 题目描述 中考考场有 N N N个房间和 N − 1 N-1 N−1双向通道,任意两个房间均可到达。现在出了一件极其灵异的事情,监控摄像头的画面里,都响起了奇怪的声音。“嘎啦,嘎啦…” 考务主任决定加强监控,现在如果在某个房间中放一个监考员,则这个房间以及所有与这个房间相连的房间都会被监控.现在他想知道至少要多少监考员可以控制所有房间,以及有多少种不同的方案数。 但这究竟是什么