话不多说，直接看题：
1.换根DP：
我们肯定不能对每一个根节点暴力求，我们不妨先求f[1]，我们发现当他的儿子作为根节点时深度和为f[1]+(n-cnt[i])-cnt[i](cnt[i]表示以i为根的节点数），这样子两遍DFS即可，下面是AC代码：
#include<bits/stdc++.h>
using namespace std;
int n,x,y,cnt[1000020],dep[1000010];
long long f[1000010];
vector<int> edge[1000010];
void dfs1(int root,int fa){
cnt[root]=1;
for(int i=0;i<edge[root].size();i++){
int w=edge[root][i];
if(w==fa) continue;
dep[w]=dep[root]+1;
dfs1(w,root);
cnt[root]+=cnt[w];
}
return;
}
void dfs2(int root,int fa){
for(int i=0;i<edge[root].size();i++){
int w=edge[root][i];
if(w==fa) continue;
f[w]=f[root]+n-2*cnt[w];
dfs2(w,root);
}
return;
}
int main(){
cin>>n;
for(int i=1;i<=n-1;i++){
scanf("%d%d",&x,&y);
edge[x].push_back(y);
edge[y].push_back(x);
}
dep[1]=0;
dfs1(1,0);
for(int i=1;i<=n;i++){
f[1]+=dep[i];
}
dfs2(1,0);
long long ans=f[1];
for(int i=2;i<=n;i++){
ans=min(ans,f[i]);
}
cout<<ans;
}2.数学问题的背包转化：
显然，我们要求的就是n个中的极大线性无关组，那么我们如何求？
只要一个数可以被比他小的组合表示出来，那么这个元素就可以删了。
如何实现？我们把每一个元素看成无穷个物品，我们判断一个元素是否可以被表示，就是看这个背包是否可以被塞满，因此变成了完全背包问题，下面是AC代码：
#include<bits/stdc++.h>
using namespace std;
int a[110],n,t,m;
bool dp[25005];
bool cmp(int a,int b){
return a<b;
}
int main(){
cin>>t;
while(t--){
cin>>n;
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
sort(a+1,a+n+1,cmp);
m=n;
dp[0]=1;
for(int i=1;i<=n;i++){
if(dp[a[i]]==1){
m--;
continue;
}
for(int j=a[i];j<=a[n];j++){
dp[j]=dp[j-a[i]]||dp[j];
}
}
cout<<m<<endl;
}
}3.水题记录位置
就是在中序遍历上找根，再变成两个区间，用区间DP即可。
那么我们如何记录前序遍历呢，直接放在一维数组实现起来比较麻烦，于是我们可以用root[i][j]来记录i--j中选的根，然后再递归下去即可。
下面是AC代码：
#include<bits/stdc++.h>
using namespace std;
int dp[40][40],n,a[40],root[40][40];
int f(int l,int r){
if(dp[l][r]>0) return dp[l][r];
if(l==r) return dp[r][r]=a[r];
if(l>r) return 1;
int g=l;
for(int i=l;i<=r;i++){
if(dp[l][r]<=a[i]+f(l,i-1)*f(i+1,r)){
dp[l][r]=a[i]+f(l,i-1)*f(i+1,r);
g=i;}
}
root[l][r]=g;
return dp[l][r];
}
void print(int l,int r){
if(l==r){
cout<<l<<" ";
return;
}
if(l>r) return;
cout<<root[l][r]<<" ";
print(l,root[l][r]-1);
print(root[l][r]+1,r);
return;
}
int main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
cout<<f(1,n)<<endl;
print(1,n);
}4.从小入手+两遍DP：
我们不妨先看一块，我们令f[k][i][x]表示第k条木板，前x个格子刷i次的最大正确粉刷格子数。
对于第k条木板，易得转移方程：f[k][i][x]=max(f[k][i-1][p]+w[p+1][x])(w[i][j]表示i--j一次刷最多可以刷对的格子数）
这样子，我们就把每一条木板刷的所有情况求出来，问题就转化成了分组背包。
我们令g[i][j]表示前i个木板刷了j次正确格子。
g[i][j]=g[i-1][k]+f[i][j-k][m].
下面是AC代码：
#include<bits/stdc++.h>
using namespace std;
int n,m,t,a[60][60],f[55][2600][55],g[55][2600],ck0[55][55],ck1[55][55],ff[55][2600];
char x;
int main(){
cin>>n>>m>>t;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
scanf(" %c",&x);
a[i][j]=x-'0';
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(a[i][j]==0){
ck0[i][j]=ck0[i][j-1]+1;
ck1[i][j]=ck1[i][j-1];
}
else{
ck1[i][j]=ck1[i][j-1]+1;
ck0[i][j]=ck0[i][j-1];
}
}
}
int x1,x2;
for(int i=1;i<=n;i++){
for(int j=1;j<=t;j++){
for(int k=1;k<=m;k++){
for(int p=0;p<=k;p++){
x1=ck0[i][k]-ck0[i][p];
x2=ck1[i][k]-ck1[i][p];
f[i][j][k]=max(f[i][j][k],f[i][j-1][p]+max(x1,x2));
}
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=t;j++){
for(int k=0;k<=j;k++){
g[i][j]=max(g[i][j],f[i][k][m]+g[i-1][j-k]);
}
}
}
cout<<g[n][t];
}
