题解 P3651 【展翅翱翔之时 (はばたきのとき)】

官方题解 我们把这种每个点入度（或者出度）为1的点称为有向环套树。显然，给出的图是一个环套树森林。我们讨论单个环套树的情况。 如果要两两可以互相交互，那么就是形成强连通。 只有一种结构可以达成：环。 所以说，我们需要找找出每个环套树的最长链。 首先找出环，然后环上的树上有多个孩子的点贪心保留权值大的点，这样变成了外向链。 然后枚举环上的每个点，把这个环破开，然后计算最长的链（你可以想象一下“6”这个数字，对就是这个意思）。 森林可能不连通，所以分别处理。最后复杂度是$O(n)$