【动态规划】树形dp
参考文章：
- 树形dp讲解（你不会后悔点进来）
- 动态规划进阶（六）：树形DP原理详解
核心思想：DFS遍历 +记忆化
- 自底向上，后序遍历，父节点最优解从子节点转移过来
状态
节点维度：dp[u][s] 表示节点u在状态s下的最优解
常见状态：
- 选择/不选当前节点
- 颜色标记（如红黑树着色问题）
- 距离限制（如树的直径）
典：没有上司的舞会
父节点最优解从子节点转移过来
- 结构：领导下属的关系类似树
- 状态：一个节点有两种状态，要么去要么不去
- 转移：
- 父节点去，子节点一定不去
- 父节点不去，子节点可以去也可以不去
- 转移方程
- d p [ f ] [ 0 ] + = m a x ( d p [ s ] [ 0 ] , d p [ s ] [ 1 ] ) dp[f][0]+=max(dp[s][0],dp[s][1]) dp[f][0]+=max(dp[s][0],dp[s][1])
- d p [ f ] [ 1 ] + = d p [ s ] [ 0 ] dp[f][1]+=dp[s][0] dp[f][1]+=dp[s][0]
const int N = 6e3+10;
int la[N],tr[N],nxt[N];//记录树
int head[N];//记录是否为根节点
int hp[N];//快乐指数
int cnt=1;
void add(int f,int s){//链式前向星 记录树结构tr[cnt]=s;nxt[cnt]=la[f];la[f]=cnt;cnt++;
}
int sum[N][2];//记录最优解
void dp(int root){//递归遍历树sum[root][0]=0;//不去sum[root][1]=hp[root];//去for(int i=la[root];i>=1;i=nxt[i]){int s=tr[i];//找儿子的值dp(s);//dfs一个儿子走到黑 自底向上sum[root][0]+=max(sum[s][1],sum[s][0]);sum[root][1]+=sum[s][0];}
}
void solve(){int n;cin>>n;forr(i,1,n){cin>>hp[i];}forr(i,1,n-1){int f,s;cin>>s>>f;add(f,s);head[s]=1;}int hd;forr(i,1,n)if(head[i]==0){hd=i;break;}// cout<<hd<<endl;dp(hd);// forr(i,1,n)cout<<sum[hd][0]<<' '<<sum[hd][1]<<endl;cout<<max(sum[hd][0],sum[hd][1])<<endl;
}