洛谷 P2015 二叉苹果树

题目链接：二叉苹果树

思路

       本题使用链式向前星存储树上的边，然后DFS搜索+简单dp。
       dp数组，dp[i][j]表示节点i及其子树保留k根树枝得到的最大苹果数。son数组存储当前节点的孩子节点的编号和当前节点与孩子节点之间的树枝上的苹果个数。
       对于dp递推公式，我们可以对每一个节点逐个分析，对于每个节点，可以将剩下的树枝条数分给左子树和右子树，当剩下的树枝只分给左子树时只需要加上当前节点与左孩子之间的树枝上的苹果个数和dp[左孩子节点编号][剩下的树枝条数-1]，即为dp[x][branchNumber] = dp[leftChild][branchNumber - 1] + appleNumber[x][leftChild]，当剩下的树枝只分给右子树时只需要加上当前节点与右孩子之间的树枝上的苹果个数和dp[右孩子节点编号][剩下的树枝条数-1]，即为dp[x][branchNumber] = dp[rightChild][branchNumber - 1] + appleNumber[x][rightChild]，当左右子树都分到了树枝时，，需要加上当前节点和左右孩子之间的树枝上的苹果个数和dp[左孩子节点编号][剩下的树枝条数 - 2]、dp[右孩子节点编号][剩下的树枝条数 - 2]，即为dp[x][branchNumber] = dp[leftChild][branchNumber - 2] + dp[rightChild][branchNumber - 2] + appleNumber[x][leftChild] + appleNumber[x][rightChild]

题解

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e2 + 10;
int head[N], edge[N], amount[N], cnt, nex[N], dp[105][105], deep[N];
int n, q;

void add(int x, int y, int num) {
  nex[++cnt] = head[x];
  head[x] = cnt;
  edge[cnt] = y;
  amount[cnt] = num;
}

void dfs(int x, ll fa) {
  vector<pair<int, int>> son;
  for (int i = head[x]; i; i = nex[i]) {
    int to = edge[i], num = amount[i];
    // 当枚举到父节点时，跳过
    if (to == fa)
      continue;
    dfs(to, x);
    // 记录当前子节点的数据
    son.push_back({to, num});
  }
  // 当当前节点没有子节点为叶子节点时直接返回上级函数
  if (son.empty()) {
    return;
  }
  // 枚举当前节点剩下的树枝条数
  for (int i = 1; i <= q; i++) {
    // 枚举分给左子树的树枝条数
    for (int j = 0; j <= i; j++) {
      int num = 0;
      // 左子树树枝条数大于0时就需要先留下当前节点和左孩子之间的树枝才能将当前节点和左子树连接起来
      if (j > 0) {
        num += son[0].second;
      }
      // 左子树树枝条数大于0时就需要先留下当前节点和左孩子之间的树枝才能将当前节点和左子树连接起来
      if (i - j > 0) {
        num += son[1].second;
      }
      // 左子树树枝条数大于0时
      if (j != 0) {
        dp[x][i] = max(dp[x][i], dp[son[0].first][j - 1] + dp[son[1].first][i - j - 1] + num);
      } else {
        // 左子树条数等于0时，说明树枝全部分给了右子树
        dp[x][i] = max(dp[x][i], dp[son[1].first][i - j - 1] + num);
      }
    }
  }
}

int main() {
  cin >> n >> q;

  for (int i = 1; i < n; i++) {
    int a, b, c;
    cin >> a >> b >> c;
    // 添加边
    add(a, b, c);
    add(b, a, c);
  }

  dfs(1, 0);

  cout << dp[1][q];
  return 0;
}