查看原题'" class='mdui-btn mdui-btn-raised'>点击加载点击跳转两次 dp 解决代替基环树 dp 所有的$A_i\rightarrow i$构成了一棵基环树我们先考虑如果基环树的子树怎么做也就是树型 dp($f_x$表示不放,$g_x$表示放)若元素$i$不投放,$$fx=\sum{A_y=x}\max(f_y,g_y)$$否则必须至少有一个元素限制$i$,不能投放$$gx=\max{A_y=x}{fy+\sum{A_z=x,z\not = y}\max(f_z,g_z)}$$找到环上的一个点,将它和它限制的那个点断开,先后进行两次树形 dp,第一次是假设环上的……