P3651 展翅翱翔之时 (はばたきのとき) 分析

· · 个人记录

做的大概是第二到第三道基环树的题，明显对环的一系列操作不熟悉。

我们知道，作为有向图，要做到两点互相连通，一定是形成一个环。同时显然，题目中所给的是一个基环森林，我们需要把每个基环树断成链，然后把它们首尾相接就可以了。具体断哪条边，需要在环上 DP。

按照基环树的一般策略，把环当作根，然后对环上每一个点跑树形 DP，把重链抽出来显然是最优的。我们可以计算其他点权和，计入贡献。

然后我们考虑环上怎么处理。对于每一个点，有两种情况：断掉 u 到环上前驱 v 的边，使环变成一个链；或者是断掉 v 的重儿子，维护当前形态。

分讨转移即可。