比较有意思的一道题
容易想到从下往上满足要求。然后这题满足最优子结构，就有个dp。设dp[i][0/1/2]为在以i为根的子树中，i所在连通块大小为1/2/3是否可行。那么dp[i][0]可行的条件就是所有儿子的dp[son_i][2]都可行。dp[i][1]可行的条件就是有一个儿子dp[i][0]可行同时其他儿子dp[i][2]都可行。dp[i][2]可行的条件是要么有一个儿子dp[i][1]可行，并且其他儿子dp[i][2]都可行，要么是有两个儿子dp[i][0]可行同时其他儿子dp[i][2]可行。然后记录一下路径，如果是从dp[i][2]转移过来的，那么要输出。
然后发现这里的dp[i][2]都没什么用，考虑直接扔掉。具体而言，从下往上做，如果这个子树大小为三，那么就扔掉，如果大于三，那么就无解。
标签：CF1833G,可行,儿子,那么,扔掉,dp From： https://www.cnblogs.com/wuhupai/p/18122651