专题班树型dp练习https://ac.nowcoder.com/acm/contest/28260#question

原问题求树上的最大独立集

Solution：仔细读题，一开始以为每次选择的地点是连续的，导致求成最大深度了。实际上是最大独立集。

debug：对于每个儿子的贡献需要累加，叶子节点需要赋初值。

vector<int>e[N];
int dp[N][2];
void dfs(int u,int fa){
	dp[u][1]=1;//叶节点赋值和每个点本身贡献
	for(auto v:e[u]){
		if(v==fa)continue;
		dfs(v,u);
		dp[u][1]+=dp[v][0];//有多个叶子，应该是+=，不是+
		dp[u][0]+=max(dp[v][1],dp[v][0]);
	}
	
}
void solve(){
	int rt;cin>>n>>rt;
	for(int i=1;i<=n-1;i++){
		int u,v;cin>>u>>v;
		e[u].push_back(v);
		e[v].push_back(u);
	}
//	memset(dp,0x3f,sizeof dp);
	dfs(rt,0);
	int ans=dp[rt][1];
// 	
cout<<ans<<endl;
}

伪装成树上dp的树上贪心

题意：给定一棵树，树上每个节点都有一个权值k[i]，表示如果染色这个点到根的树链上能免费染色距离i不超过k[i]的点，求最少染色次数

Solution:贪心还是需要慢慢分析，中间更新最大值也算dp(bushi).

  • 由于每个点都只会被他子树以内的点染色，我们每次维护它的子树除了它能染色的最大高度。如果为0，说明之前的贪心策略无法满足，需要多花费一次染色次数，

  • 考虑选择能贡献最大的点，这个值也需要一直维护更新，具体来说就是u这个点k值和max(v的k值)-1去比较。

  • 在花费一次染色机会的时候，用k去维护f

//看似树上dp，其实树上贪心
//由于本题染色是受到子节点影响
//从下向上思考问题，如果当前所有子节点上传的值都无法染色该点，我们
//只能考虑在之前没被染色的值里选一个最大的，所以我们需要维护这个
int k[N];
int f[N];
//k[i]表示以i为子树的所有点所能向上影响最大值
//f[i]表示当前实际方案中，i的子树最多能向上跳到哪
int cnt=0;
vector<int>e[N];
void dfs(int x){
	for(auto v:e[x]){
		dfs(v);
		k[x]=max(k[x],k[v]-1);
		f[x]=max(f[x],f[v]-1);
	}
	if(f[x]==0){
		//说明当前这个点在当前方案下已经无法染色了
		//做出改变：再选一个点染色，在所有备选的点中选取最大值
		f[x]=k[x];
		cnt++;
	}
}
void solve(){
	cin>>n;
	for(int i=2;i<=n;i++){
		int x;cin>>x;
		e[x].push_back(i);
	}
	for(int i=1;i<=n;i++)cin>>k[i];
	dfs(1);
	cout<<cnt<<endl;
}

https://www.nowcoder.com/discuss/353157393250983936?sourceSSR=search

专题班树型dp例题https://ac.nowcoder.com/acm/contest/28258

求树的重心

Solution：只需要枚举每个点,比较重儿子大小和父节点以上的大小，比较出最大连通块大小的最小值

int sz[N];
int son[N];
vector<int>e[N];
void dfs(int u,int fa){
	sz[u]=1;
	for(auto v:e[u]){
		if(v==fa)continue;
		dfs(v,u);
		
		if(son[u]<sz[v])son[u]=sz[v];
		sz[u]+=sz[v];
	}
}
void solve(){
	while(cin>>n){
		for(int i=1;i<=n;i++)e[i].clear();
		fill(sz,sz+n+1,0);
		for(int i=1;i<=n-1;i++){
			int u,v;cin>>u>>v;
			e[u].push_back(v);
			e[v].push_back(u);
		}
		dfs(1,0);
		int ans=1e9;int pos=0;
		for(int i=1;i<=n;i++){
			int tmp=max(son[i],n-sz[i]);
			if(ans>tmp){
				ans=tmp;
				pos=i;
			}
		}
		cout<<pos<<" "<<ans<<endl;
		
		
	}
}

树上问题选讲 - hztmax0 - 博客园 (cnblogs.com)

222222222222222树形背包总结 - lnzwz - 博客园 (cnblogs.com)

刷题：ACM 树上背包DP总结 - liweihang - 博客园 (cnblogs.com)