CF1833G Ksyusha and Chinchilla 题解

首先，若 \(n \bmod 3 \neq 0\)，则一定无解。

考虑 \(n \bmod 3 = 0\) 的情形：

首先肯定是先进行一遍树形 dp，求出树上每个节点 \(x\) 的子树大小 \(size_x\)。

若当前节点的 \(size\) 值 \(=3\)，则说明需要切断当前节点于其父节点的连边，使得其子树成为一个大小为 \(3\) 的单独连通块。

于是将 \(cut_{id}\)（\(cut_i\) 表示第 \(i\) 条边是否需要切断，\(id\) 表示当前节点与其父节点连边的编号）设为 \(1\)，并且为了方便接下来的处理，将 \(size_x\) 设为 \(0\) 即可。

否则说明这颗子树无法贡献答案的，直接递归回溯即可。

注意多测清空！

核心代码：

//树形dp
void dfs(int x,int pre){ //pre是x的父节点
	sz[x]=1;
	if(!ans) return; //无法贡献答案就递归回溯
	int nid=0;
	for(auto i:G[x]){
		if(i.to==pre) nid=i.id; //记录父节点
		else dfs(i.to,x),sz[x]+=sz[i.to]; //求子树大小
	}
	if(sz[x]==3) sz[x]=0,cut[nid]=1; //切断x和pre间的连边
	else if(sz[x]>3) ans=0; //这颗子树无法贡献答案
}