【算法笔记】 树形DP算法总结

定义：树形DP也叫树状DP，即在树上进行的DP，是DP中较为复杂一类

1：主体

即like拓扑排序，从叶子节点向上更新其父节点，从而进行dp，确保先更新的子节点去更新其父节点，一般使用dfs形式：

void dfs(ll u,ll fa)
{
	dp[u]=1;
	for(auto c:G[u])
	{
		if(c!=fa)
		{
			dfs(c,u);
			dp[u]+=dp[c];
		}
	}
}

【例1.2】洛谷P1352 没有上司的舞会

//P1352 没有上司的舞会
//2024.3.27 12：38

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 500005;
#define mod 1000000007
#define inf 1e18
#define YES cout<<"YES"<<'\n';
#define NO cout<<"NO"<<'\n';
#define lc p<<1
//左子节点
#define rc p<<1|1

vector<ll>a[N],sz(N),f(N),g(N),rot(N);
void dfs(ll u,ll fa)
{
	//sz[u]=1;
	for(auto c:a[u])
	{
		if(c!=fa)
		{
			dfs(c,u);
			f[u]+=g[c];//选择了u就不能选择他儿子
			g[u]+=max(g[c],f[c]);//不选择u也可以不选择儿子，也可以选择
		}
	}
}
void solve()
{
	ll n;cin>>n;
	for(ll i=1;i<=n;i++) cin>>sz[i],f[i]=sz[i];//初始化每个人的兴趣度
	for(ll i=1;i<n;i++)
	{
		ll x,y;cin>>x>>y;
		a[x].push_back(y);
		a[y].push_back(x);
		rot[y]++;
	}
	ll d=0;
	for(ll i=1;i<=n;i++)
	{
		if(!rot[i])
		{
			d=i;//找boss
			break;
		}
	}
	dfs(d,0);
	cout<<max(g[d],f[d])<<'\n';
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	//ll t;cin>>t;
	//while(t--) 
	solve();
	return 0;
}

2：树形背包

3：换根DP