树形dp(1) P2015二叉苹果树

胡乱分析

实际上树形dp就是在树上进行的dp，这个题类似于01背包的一种dp的感觉，也是树形dp的模板题第一题。状态转移是从下到上的所以是回溯的时候进行的dp
转移方程
dp[p][j]=max(dp[p][j],dp[p][j-k-1]+dp[to][k]+w)
其中dp[i][j]代表i节点包含j条边所具有的最大权值和那么显然最终答案就是dp[1][q]
为什么是j-k-1因为要保证节点之间相互连接，剩下的就是从下向上dp了
还有就是dfs函数计算的是当前节点下有多少的边，dp的时候不能分的边比原本包含的边要多吧

代码

#include <bits/stdc++.h>
using namespace std;
int n,m;
struct node
{
  int to,sum;
};
vector<node> G[105];
int dp[105][105],num[105];
int dfs(int now,int fa)
{
  for(int i=0;i<G[now].size();i++)
  if(G[now][i].to!=fa)
  num[now]+=dfs(G[now][i].to,now);
  if(!num[now])
  return 1;
  else
  return num[now]+1;
}
void solve(int now,int fa)
{
  for(int i=0;i<G[now].size();i++)
  if(G[now][i].to!=fa)
  {
    solve(G[now][i].to,now);
    for(int j=m;j;j--)
    for(int k=0;k<j&&k<=num[now];k++)
    dp[now][j]=max(dp[now][j],dp[now][j-k-1]+dp[G[now][i].to][k]+G[now][i].sum);
  }
}
int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin>>n>>m;
  for(int i=1;i<=n-1;i++)
  {
    int st,ed,sum;
    cin>>st>>ed>>sum;
    G[st].push_back((node){ed,sum});
    G[ed].push_back((node){st,sum});
  }
  dfs(1,1);
  solve(1,1);
  cout<<dp[1][m];
}

尝试后发现不加dfs也是对的

#include <bits/stdc++.h>
using namespace std;
int n,m;
struct node
{
  int to,sum;
};
vector<node> G[105];
int dp[105][105],num[105];
void solve(int now,int fa)
{
  for(int i=0;i<G[now].size();i++)
  if(G[now][i].to!=fa)
  {
    solve(G[now][i].to,now);
    for(int j=m;j;j--)
    for(int k=0;k<j;k++)
    dp[now][j]=max(dp[now][j],dp[now][j-k-1]+dp[G[now][i].to][k]+G[now][i].sum);
  }
}
int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin>>n>>m;
  for(int i=1;i<=n-1;i++)
  {
    int st,ed,sum;
    cin>>st>>ed>>sum;
    G[st].push_back((node){ed,sum});
    G[ed].push_back((node){st,sum});
  }
  solve(1,1);
  cout<<dp[1][m];
}