【HAOI2010】软件安装

题面

https://www.luogu.org/problem/P2515

题解

因为一个点出去一条父边，所以可能形成一个树，但也有可能形成一个环，环上的点都不能选。

$tarjan$找环，然后就是树形背包（$gyfan$昨天还在念叨的“神仙题”）

可能有点注意的，一棵树去掉一条从根节点开始的链，应该是形成很多棵子树（这些子树的根节点一定是删去的点的儿子，并且它自己没有被删去），比较麻烦，但是直接把环上的价值设为$INF$就好了。

代码没有。