[ZJOI2008] 骑士 - 基环树dp

一类基环树dp都是这个套路吧

随便拆掉环上的一条边

然后跑树形dp,设\(f[i][0/1]\)表示以第\(i\)个人为根的子树,第\(i\)个人选或不选,能收获的最大值

以断点\(u,v\)为根分别跑基环树,每个连通块答案就是 \(max(f[u][0],f'[v][0])\)

血:两个骑士可能相互憎恨,形成重边

上一篇:【ZJOI2008】骑士(基环树+DP)


下一篇:P2607 [ZJOI2008]骑士