比较有意思的一道题容易想到从下往上满足要求。然后这题满足最优子结构，就有个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]

首先，若\(n\bmod3\neq0\)，则一定无解。考虑\(n\bmod3=0\)的情形：首先肯定是先进行一遍树形dp，求出树上每个节点\(x\)的子树大小\(size_x\)。若当前节点的\(size\)值\(=3\)，则说明需要切断当前节点于其父节点的连边，使得其子树成为一个大小为\(3\)的单独连通块。

题意：思路：当$n\not\equiv0\space(mod\space3)$时，无解；当$n\equiv0\space(mod\space3)$时，设$size_u$表示以$u$为根的子树还剩余的节点个数，自根节点向叶子节点递归，返回时进行处理节点$u$：设节点$u$的子节点为长度为$len$的序列$v$，设