树形DP（树形背包+换根DP）

树形DP

没有上司的舞会

家常便饭了，写了好几遍，没啥好说的，正常独立集问题。

int head[B];
int cnt;
struct node
{int v,nxt;
}e[B<<1];
void modify(int u,int v)
{e[++cnt].nxt=head[u];e[cnt].v=v;head[u]=cnt;
}
int a[B];
int f[B][5];
int n;
void dfs(int u,int pre)
{for (int i=head[u];i;i=e[i].nxt){int v=e[i].v;if (v==pre) continue;dfs(v,u);f[u][1]+=f[v][0];f[u][0]+=max(f[v][0],f[v][1]);}
}
void work()
{cin>>n;for (int i=1;i<=n;i++) f[i][1]=read();for (int i=1;i<n;i++){int v=read(),u=read();modify(u,v);modify(v,u); }dfs(1,0);cout<<max(f[1][0],f[1][1]);
}

选课

树上背包问题。

说说自己犯的错误

式子推得太慢
滚动数组特别容易记混状态，尤其是背包，因为是从大到小更新，如果在枚举到大数的时候发生转移却用的小的，那么更新的答案必然是错误的，这个问题我调了一下午，就是滚动数组的错误，一定切记，对于逆序的滚动数组问题，一定好想好当前所需状态是否已经更新，而不是借用上一维的状态，这种错误最容易犯在背包上！！
这个题目优化点在于，用一个虚拟点来连接森林，这样就不用再写一遍了

#include<bits/stdc++.h>
using namespace std;
int read(){int x;scanf("%d",&x);return x;}
const int B=1e6+10;
const int inf=0x3f3f3f3f;
int T;
int n,m;
int f[309][309];
int dp[309][309];
int a[B];
int head[B];
int cnt;
struct node
{int v,nxt;
}e[B<<1];
void modify(int u,int v)
{e[++cnt].nxt=head[u];e[cnt].v=v;head[u]=cnt;
}
int fa[B];
int vis[B];
void dfs(int u,int pre)
{f[u][1]=a[u];for (int i=head[u];i;i=e[i].nxt){int v=e[i].v;if (v==pre) continue;dfs(v,u);}for (int i=head[u];i;i=e[i].nxt){int v=e[i].v;if (v==pre) continue; for (int j=m;j>=1;j--){for (int k=1;k<=j;k++)dp[u][j]=max(dp[u][j],dp[u][j-k]+f[v][k]);//f[u][j]=dp[u][j-1]+a[u];//因为我们的j是倒序枚举，先更新大的在更新小的，那么dp[u][j-1]并不是当前已经对v//点进行操作完毕的 dp，而是上一维度 }for (int j=1;j<=m;j++) f[u][j]=dp[u][j-1]+a[u];//放在外面就是正确的，这是因为用的是当前维度下的dp，滚动数组容易反的错误 }
} 
int ans[B];
int num;
int F[B];
void work()
{cin>>n>>m;for (int i=1;i<=n;i++){fa[i]=read();a[i]=read();modify(fa[i],i);modify(i,fa[i]);}for (int i=1;i<=n;i++){if (!fa[i]){dfs(i,0);ans[++num]=i;}}for (int i=1;i<=num;i++){for (int j=m;j>=1;j--){int x=ans[i];for (int k=0;k<=min(m,j);k++)F[j]=max(F[j],F[j-k]+f[x][k]);}	}cout<<F[m]; 
}
int main()
{T=1;while (T--) work();return 0;
}

积蓄程度

题面：见ACwing287

思路：

换根DP的常规思路

有下往上递推一遍
再由上往下递推一遍

我们先来想如果根节点固定的时候如何做，比较容易的DP，其实也就是递推，没有任何决策问题。

$d [u]$ 表示以 $u$ 为根节点的最小流量。通过题目可以知道，一条路径上的流量取决于最小流量边，所以这是一个维护最小值的问题。

转移有
$d[u]=\sum \min\{d[v],w\}$
再来考虑如何换根。

先来考虑由根节点换到儿子会发生什么变化

我们会发现， $d [1]$ 中需要去掉 $d [2]$ 做出的贡献，即 $d[1]-\min\{d[2],w\}$

$d [2]$ 需要加入 $d [1]$ 的贡献，即 $d[2]+\min\{d[1],w\}$

我来思考，如果是在树中间换根怎么办，我们发现，父亲节点还需要同时加入父亲父亲的节点情况。

在这里插入图片描述

比如绿色部分，可是这条边比较难表示，不容易找到 $w$ ，如果我们看成 $2$ 节点就是根节点，不再是父亲节点的时候，此时的值刚好就是 $2$ 当根的值，我们用 $f [2]$ 表示 $2$ 为根的最大值。那么在转移的时候我们就不需要考虑由父亲父亲的情况。转移由
$f[v]=d[v]+\min\{w,f[u]-\min\{w,d[v]\}\}$

对于度数只为1的还需要特别注意，度数唯一不一定是叶子结点，也可能是根节点，当换根时，根节点变成叶子结点， $f[u]-\min\{w,d[v]\}$ 变成 $0$ ，实际上应该直接加入边值 $w$ ，所以需要特别判断。

换根时候的注意点

必须一直保持根和儿子换，而不是父亲和儿子换。
根节点和叶子结点要注意

#include<bits/stdc++.h>
using namespace std;
int read(){int x;scanf("%d",&x);return x;}
const int B=1e6+10;
const int inf=0x3f3f3f3f;
int T;
int n;
int head[B],cnt;
struct node
{int v,nxt,w;
}e[B<<1];
void modify(int u,int v,int w)
{e[++cnt].nxt=head[u];e[cnt].v=v;e[cnt].w=w;head[u]=cnt;
}
int f[B];
int d[B];
int du[B];
void dfs1(int u,int pre)
{for (int i=head[u];i;i=e[i].nxt){int v=e[i].v;int w=e[i].w;if (v==pre) continue;dfs1(v,u);if (du[v]!=1) d[u]+=min(d[v],w);else d[u]+=w;}
} 
void dfs2(int u,int pre)
{for (int i=head[u];i;i=e[i].nxt){int w=e[i].w;int v=e[i].v;if (v==pre) continue;if (du[u]==1) f[v]=d[v]+w;else f[v]=d[v]+min(w,f[u]-min(d[v],w));dfs2(v,u);}
}
void work()
{cin>>n;cnt=0;memset(head,0,sizeof(head));for (int i=1;i<=n;i++){f[i]=0;d[i]=0;du[i]=0;}for (int i=1;i<n;i++){int u=read(),v=read(),w=read();modify(u,v,w); du[u]++; du[v]++;modify(v,u,w);}dfs1(1,0); f[1]=d[1];dfs2(1,0);int ans=0;for (int i=1;i<=n;i++) ans=max(ans,f[i]);cout<<ans<<"\n";
}
int main()
{T=read();while (T--) work();return 0;
}
/*
1
3
1 2 1
2 3 1
*/