树形DP的经典------二叉苹果树

题意概述

1. 一棵苹果树，有边权，保留一定数量的边，问边权之和最大多少

思路

1. 为什么和01背包有关----每一个分叉都有选和不选的两种可能
2. 表示以i为根的子树选择了j条边能达到的最大权值
3. 子树到底选不选
4. 如果不选的话
5. 如果选的话
   注意这里是的原因是，选择了子树后又会向连一条边
6. 那么
7. 这样其实就是一个树上01背包问题了
8. 这个题还需要存每一棵子树的边数

代码

#include <bits/stdc++.h>
#define endl '\n'
// #define int long long
using lli = long long;
using ull = unsigned long long;

inline int read()
{
    int x = 0, flag =  1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if (ch == '-')
        {
            flag = -1;
        }
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * flag;
}

std::vector<int> t[1100];
int N = 0, Q = 0;
int val[1100];
int cnt = 0;
int head[1100];
int dp[1100][1100];
int branch[1100];
struct Edge
{
    int start;
    int weight;
    int terminus;
    int next;
}edge[210];

void AddEdge(int start, int terminus, int weight)
{
    edge[++cnt].start = start;
    edge[cnt].terminus = terminus;
    edge[cnt].weight = weight;
    edge[cnt].next = head[start];
    head[start] = cnt;
}

void dfs(int s, int fa)
{
    for (int i = head[s]; i != -1; i = edge[i].next)
    {
        int end = edge[i].terminus;
        if (end == fa) continue;
        dfs(end, s);
        branch[s] += branch[end] + 1;
        int tmp1 = std::min(Q, branch[s]), tmp2 = 0;
        for (int j = tmp1; j >= 0; j--) // 01背包倒序存防止重复
        {
            tmp2 = std::min(j - 1, branch[end]);
            for (int k = tmp2; k >= 0; k--)
            {
                dp[s][j] = std::max(dp[s][j], dp[s][j - k - 1] + dp[end][k] + edge[i].weight);
            }
        }
    }
}

signed main()
{
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    //int s = clock();
    memset(head, -1, sizeof(head));
    N = read(), Q = read();
    int u = 0, v = 0, w = 0;
    for (int i = 1; i <= N - 1; i++)
    {
        u = read(), v = read(), w = read();
        AddEdge(u, v, w);
        AddEdge(v, u, w);
    }
    dfs(1, -1);
    printf("%d\n", dp[1][Q]);
    //int t = clock();
    //std::cout << t - s << endl;
    return 0;
}