一类基环树dp都是这个套路吧
随便拆掉环上的一条边
然后跑树形dp,设\(f[i][0/1]\)表示以第\(i\)个人为根的子树,第\(i\)个人选或不选,能收获的最大值
以断点\(u,v\)为根分别跑基环树,每个连通块答案就是 \(max(f[u][0],f'[v][0])\)
血:两个骑士可能相互憎恨,形成重边
2024-02-24 12:02:28
一类基环树dp都是这个套路吧
随便拆掉环上的一条边
然后跑树形dp,设\(f[i][0/1]\)表示以第\(i\)个人为根的子树,第\(i\)个人选或不选,能收获的最大值
以断点\(u,v\)为根分别跑基环树,每个连通块答案就是 \(max(f[u][0],f'[v][0])\)
血:两个骑士可能相互憎恨,形成重边