题目大意:
你现在有一棵树,每次你可以选择一个点,将这个点变成根,然后递归处理他的大小不为 1 的儿子们。
请问度数为 1 的点的数量最多有多少。
\(n \le 2 \times 10^5\)。
解题思路:
考虑简化他的题意,考虑什么时候停止,就是当他任意一条边上的两个点至少有一个被选择当根的时候、
那么对于所有没被选中的点,他在最终的状态下一定是叶子。
而对于选中的点,因为他一定有儿子,所以当根只有一个儿子时答案会多一。
而只有一个儿子当且仅当他是叶子。
也就是你要选出一个独立集,如果他不包含所有的叶子,那么答案会多一。
也就是设个 \(f_{u,0/1,0/1}\) 表示 \(u\) 子树内,它本身选没选,有没有全选叶子的最大大小。
这题的难点是转化题意,自己做的时候凭感觉猜了个与独立集相近的东西,以后想不到啥对的东西可以多往这些概念上想。
