题意:在树上加边,使得每个点在切仅在一个环上,问最少的加边次数,如果无法做到,输出-1.添加的不能是自环,重边,即一个环上的点数至少为3
比较突破常规思维的树dp
dp[u][2]:表示u为根的子树,有一条剩余的链没有属于任何一个环,其他点均完成任务这条链的点数>=2
//即点u要和其他点形成一条链,那肯定是跟某个儿子开始,那么先让某个儿子孤立出来,这个儿子可能只是自己孤立出来,所以dp[v][1],可能连带着孤立出一条链dp[v][2]选较小的那个花费,那么其他点都是已经完成任务了,其他点完成任务的总代价就是sum-dp[v][0]; 最终就是让sum-dp[v][0]+min(dp[v][1]dp[v][2]);最小