CF1984E Shuffle 题解

这道题怎么出现在点分树的专题题单里…不过也算广义的点分树吧。

给定一棵 $n$ 个节点的树，让你求一个点分树让它的叶子尽量多。

特别地，点分树的根节点如果度数为 $1$（即选的分治中心本身是叶子），那么它也算一个叶子。

$2\le n\le 2\times 10^5$。

发现从叶子开始取比不从叶子开始取一定严格不劣，所以问题对于树上的每个叶子，把这个叶子扣掉，问剩下的节点的最大独立集是多少，首先求树上最大独立集就是经典树形 dp 入门题没有上司的舞会，

那扣掉一个叶子的操作相当于允许至多一个叶子节点和它的父亲同时被选择，那我们把这一个维度压进 dp 状态里，我们令 $f_{u,0/1,0/1}$ 表示 $u$ 本身选了/没选，有 $0/1$ 个叶子节点和它父亲同时被选的方案数。

当第二维为 $0$ 的时候转移就是没有上司的舞会，$f_{u,0,1}$ 是在 $f_{u,0,0}$ 的基础上挑选其中一个儿子 $v$ 将 $\max{f_{v,0,0},f_{v,1,0}}$ 变成 $\max{f_{v,0,1},f_{v,1,1}}$，$f_{u,1,1}$ 则是在 $f_{u,1,0}$ 的基础上挑选其中一个儿子 $v$ 将 $f_{v,0,0}$ 变成 $f_{v,0,1}$（所以要记录记录差的最大值 $mx0,mx1$）： $$ f_{u,0,0}=\sum_{v\in son(u)} \max{f_{v,0,0},f_{v,1,0}}\ f_{u,0,0}=\sum_{v\in son(u)} f_{v,0,0}\ $$

附上代码：

#include<bits/stdc++.h>
#define FL(i,a,b) for(int i=(a);i<=(b);i++)
#define FR(i,a,b) for(int i=(a);i>=(b);i--)
#define ll long long
using namespace std;
const int MAXN = 3e5 + 01;
int n;
int f[MAXN][2][2];
vector<int>G[MAXN];
void dfs(int u,int fa){
	f[u][1][0]=1,f[u][0][0]=f[u][1][1]=f[u][0][1]=0;
	int mx0=0,mx1=0;
	for(int v:G[u]){
		if(v==fa) continue;
		dfs(v,u);
		f[u][1][0]+=f[v][0][0];
		f[u][0][0]+=max(f[v][1][0],f[v][0][0]);
		mx0=max(mx0,max(f[v][0][1],f[v][1][1])-max(f[v][0][0],f[v][1][0]));
		mx1=max(mx1,f[v][0][1]-f[v][0][0]);
		if(G[v].size()==1) mx1=max(mx1,1);
	}
	f[u][0][1]=f[u][0][0]+mx0;
	f[u][1][1]=f[u][1][0]+mx1;
//	printf("u=%d %d %d %d %d\n",u,f[u][1][0],f[u][0][0],f[u][1][1],f[u][0][1]);
}
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		scanf("%d",&n);
		FL(i,1,n) G[i].clear();
		FL(i,1,n-1){
			int u,v;
			scanf("%d%d",&u,&v);
			G[u].push_back(v);
			G[v].push_back(u);
		}
		dfs(1,0);
		printf("%d\n",max({f[1][0][0]+(G[1].size()==1),f[1][0][1],f[1][1][0],f[1][1][1]}));
	}
}