P2607

没有讨厌的人的舞会 题解

题目描述类似一道树形dp板子没有上司的舞会， 区别在于这不是一棵树而是一张图。每个人只能讨厌一个人，但是一个人可能被讨厌很多遍，所以共有n点n边，每个点的出度一定为1，可得这是一个由一棵树和一条边组成的基环树。

对于其中唯一的环，断环为链。找到环上的一点root，断开root到fa[root]的边，把图变成一棵树，然后用树形dp解决（同没有上司的舞会）。但是这样得出的答案缺少了root与fa[root]之间的限制，所以我们可以强制限制。先强制不选它的父亲对它进行dp，记录为t；再强制不选它对它的父亲进行dp，记录为p，两者取max加入ans即可。