专栏文章

树形dp

kkamikuQAQ
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minxmsm4
此快照首次捕获于
2025/12/02 10:01
3 个月前
此快照最后确认于
2025/12/02 10:01
3 个月前
查看原文

树形dp

树上子树问题 例题B3861子树和

首先依旧是图论老惯例先建双向边树，子树和的概念就是就是子树中有多少个结点，然后以1为祖宗一直从下用dfs遍历，需要注意的是在找儿子的时候一定要先递归再算答案，直到找到了叶子结点再把答案给自己的祖先
CPP
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e3+7;
vector<int>g[maxn];
void addline(int u,int v) {
	g[u].push_back(v);
	g[v].push_back(u);
}
int siz[maxn];
void dfs(int u,int fa) {
	siz[u]=1;
	for(int i=0;i<g[u].size();i++) {
		int v=g[u][i];
		if(v!=fa) {
			dfs(v,u);
			siz[u]+=siz[v];
		}
	}
}
int main() {
	int n;
	cin>>n;
	for(int i=2;i<=n;i++) {
		int f;
		cin>>f;
		addline(i,f);
	}
	dfs(1,0);
	for(int i=1;i<=n;i++) {
		cout<<siz[i]<<'\n';
	}
	return 0;
}

P1352

本题多加了要么选下面一个点可以选或不选的条件，于是我们选定一个点为起点赋初始值为这个点的点权，然后照例跑dfs如果子树的点权和为负数则+0作为不选的条件，否则选上
CPP
#include<bits/stdc++.h>
using namespace std;
const int maxn = 16007;
vector<int>g[maxn];
void addline(int u,int v) {
	g[u].push_back(v);
	g[v].push_back(u);
}
int r[maxn],dp[maxn];
void dfs(int u,int fa) {
	dp[u]=r[u];
	for(int i=0;i<g[u].size();i++) {
		int v=g[u][i];
		if(v!=fa) {
			dfs(v,u);
			dp[u]+=max(0,dp[v]);
		}
	}
}
signed main() {
	int n;
	cin>>n;
	for(int i=1;i<=n;i++) {
		cin>>r[i];
	}
	for(int i=1;i<n;i++) {
		int a,b;
		cin>>a>>b;
		addline(a,b);
	}
	dfs(1,0);
	int maxx=-1e9;
	for(int i=1;i<=n;i++) {
		maxx=max(maxx,dp[i]);
	}
	cout<<maxx;
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...