LG 2607 [ZJOI2008]骑士

zcmimi at 
查看原题'" class='mdui-btn mdui-btn-raised'>点击加载点击跳转将一个骑士与他最痛恨的人连边先考虑这个如果是树型 dp:$f_x$表示不取$x$,$g_x$表示取$x$$$fx=\sum \max(f{to},g_{to})\gx=\sum f{to}$$我们可以用两次树型 dp 代替基环树 dp 第一次: 选择$x$,不选择$x$最痛恨的人第一次: 选择$x$最痛恨的人,不选择$x$……