树形DP，顾名思义就是在树上DP
T1 B3861 子树和
首先使用数组sz来存储答案(代码中是dis因为sz被【数据删除】了)
可以发现要先算出子树的答案再算出根的答案，所以枚举顺序是自底向上
那么，对于每个点：
定义状态：sz[i]表示根为i的子树的答案
确定答案：sz[i]
状态转移：sz[i]+=sum(sz[i的子节点])
初始值&边界：sz[i]=1
#include<bits/stdc++.h>
#define int long long
#define endl "\n"
using namespace std;
const int maxn=1e6+5,mod=1e9+7,inf=1e18;
int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0' && ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
void write(int x){if(x<0){putchar('-'),x=-x;}if(x>9){write(x/10);}putchar(x%10+'0');return;}
int fpow(int a,int b,int p){if(b==0){return 1;}int res=fpow(a,b/2,p)%p;if(b%2==1){return((res*res)%p*a)%p;}else{return(res*res)%p;}}
int n;
int dis[maxn];
vector<int>vt[maxn];
void dfs(int x,int ff){dis[x]=1;for(int v:vt[x]){if(v==ff)continue;dfs(v,x);dis[x]+=dis[v];}
}
signed main(){cin>>n;for(int i=2;i<=n;i++){int x;cin>>x;vt[i].push_back(x);vt[x].push_back(i);}dfs(1,0);int maxi=0;for(int i=1;i<=n;i++){cout<<dis[i]<<endl;}return 0;
}T2 P1122 最大子树和
其实就是子树和这道题加了一个判断
如果根加上子树的答案比根的答案大就更新根的答案(跟子序列同理)
定义状态：dp[i]表示根为i的子树的答案
确定答案：max(dp[i])
状态转移：dp[i]=max(dp[i],dp[x]+dp[i的子节点])
初始值&边界：dp[i]=a[i]
#include<bits/stdc++.h>
#define int long long
#define endl "\n"
using namespace std;
const int maxn=1e6+5,mod=1e9+7,inf=1e18;
int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0' && ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
void write(int x){if(x<0){putchar('-'),x=-x;}if(x>9){write(x/10);}putchar(x%10+'0');return;}
int fpow(int a,int b,int p){if(b==0){return 1;}int res=fpow(a,b/2,p)%p;if(b%2==1){return((res*res)%p*a)%p;}else{return(res*res)%p;}}
int n;
int dp[maxn],val[maxn];
vector<int>vt[maxn];
void dfs(int x,int ff){dp[x]=val[x];for(int v:vt[x]){if(v==ff)continue;dfs(v,x);dp[x]=max(dp[x],dp[x]+dp[v]);}
}
signed main(){cin>>n;for(int i=1;i<=n;i++){cin>>val[i];}for(int i=1;i<n;i++){int x,y;cin>>x>>y;vt[y].push_back(x);vt[x].push_back(y);}dfs(1,0);int maxi=-inf;for(int i=1;i<=n;i++){maxi=max(maxi,dp[i]);}cout<<maxi;return 0;
}T3 P1352 没有上司的舞会
这里因为涉及选或不选，我们再加一个维度表示选或者不选
定义状态：dp[i][0/1]表示根为i的子树的答案
确定答案：max(dp[i][0],dp[i][1]),因为树无论怎么变，答案都不变，所以可以用1号店替代
状态转移：dp[i][0]+=max(dp[i的子节点][0],dp[i的子节点][1])
dp[i][1]+=dp[i的子节点][0]
初始值&边界：dp[i][1]=a[i],dp[i][0]=0
#include<bits/stdc++.h>
#define int long long
#define endl "\n"
using namespace std;
const int maxn=1e6+5,mod=1e9+7,inf=1e18;
int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0' && ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
void write(int x){if(x<0){putchar('-'),x=-x;}if(x>9){write(x/10);}putchar(x%10+'0');return;}
int fpow(int a,int b,int p){if(b==0){return 1;}int res=fpow(a,b/2,p)%p;if(b%2==1){return((res*res)%p*a)%p;}else{return(res*res)%p;}}
int n;
int dp[maxn][2],val[maxn];
vector<int>vt[maxn];
void dfs(int x,int ff){dp[x][1]+=val[x];for(int v:vt[x]){if(v==ff)continue;dfs(v,x);dp[x][0]+=max(dp[v][0],dp[v][1]);dp[x][1]+=dp[v][0];}
}
signed main(){cin>>n;for(int i=1;i<=n;i++){cin>>val[i];}for(int i=1;i<n;i++){int x,y;cin>>x>>y;vt[y].push_back(x);vt[x].push_back(y);}dfs(1,0);cout<<max(dp[1][0],dp[1][1]);return 0;
}T4 P2016 战略游戏
与上一题类似，只是变成了最小值，但不同的是，就算父亲放了，儿子也可以放，但父亲没放，儿子就必须放
#include<bits/stdc++.h>
#define int long long
#define endl "\n"
using namespace std;
const int maxn=1e6+5,mod=1e9+7,inf=1e18;
int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0' && ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
void write(int x){if(x<0){putchar('-'),x=-x;}if(x>9){write(x/10);}putchar(x%10+'0');return;}
int fpow(int a,int b,int p){if(b==0){return 1;}int res=fpow(a,b/2,p)%p;if(b%2==1){return((res*res)%p*a)%p;}else{return(res*res)%p;}}
int n;
int dp[maxn][2],val[maxn];
vector<int>vt[maxn];
void dfs(int x,int ff){dp[x][1]=1;dp[x][0]=0;for(int v:vt[x]){if(v==ff)continue;dfs(v,x);dp[x][1]+=min(dp[v][0],dp[v][1]);dp[x][0]+=dp[v][1];}
}
signed main(){memset(dp,0x3f3f3f3f,sizeof(dp));cin>>n;for(int i=1;i<=n;i++){int x,y,k;cin>>x>>y;while(y--){cin>>k;vt[k].push_back(x);vt[x].push_back(k);}}dfs(0,0);cout<<min(dp[0][0],dp[0][1]);return 0;
}