经典的题要敢于有不同的做法

懵逼的 题目

传送至 luogu

扯淡的 题解

树形DP…经典题目没什么好说的
然后我打了个普通树形DP × 奇怪的背包(忘了叫啥惹)
TLE TLE
然后就放下了…今天loli突然让打这道于是就用了那个什么 [左儿子右兄弟] 做了一波
TLE TLE
然后Refun真dalao让我在大牛上交一遍….就TM过了…
然后把第一次的那个树形 × 背包交了一遍…也TM过了…
跑的还比第一个快…
一开始在CV上交过了还以为CV数据水
现在才知道是LG测评姬慢 CTL

沙茶的 代码

树形 × 背包

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <queue>
#define MAXN (300 + 5)
#define INF (6000)
const int root = 0;
using namespace std;
struct edg
{
    int from;
    int to;
    int next;
} b[MAXN];
int cntb = 0;
int g[MAXN];

int n, m;
int w[MAXN];
int du[MAXN];
int fa[MAXN];
int f[MAXN][MAXN];
int fv[MAXN];

int dfs(int, int);// dfs(i, j)以 i 为根, 选 j 门课最大的收益
void adn(int, int);
int bb(int, int);//
int main()
{
    memset(f, -1, sizeof(f));
    scanf("%d%d", &n, &m);
    int srx, sry;
    for (int i = 1; i <= n; i++)
    {
        scanf("%d%d", &srx, &sry);
        adn(srx, i);
        fa[i] = srx;
        w[i] = sry;
    }
    int ans = dfs(root, m + 1);
    printf("%d", ans);
    return 0;
}
void adn(int fr, int to)
{
    b[++cntb].next = g[fr];
    b[cntb].from = fr;
    b[cntb].to = to;
    g[fr] = cntb;
}
int dfs(int dq, int dqm)
{
    f[dq][0] = 0;
    f[dq][1] = w[dq];
    f[dq][dqm] = w[dq];
    dqm--;
    for (int i = g[dq]; i; i = b[i].next)
    {
        for (int j = 0; j <= dqm; j++)
            if (f[b[i].to][j] == -1)
            {
                dfs(b[i].to, j);
                if (f[b[i].to][j] == -1)
                {
                    f[b[i].to][j] = -INF;
                }
            }
    }
    dqm++;
    f[dq][dqm] += bb(dq, dqm - 1);
    return f[dq][dqm];
}
int bb(int r, int v)
{
    memset(fv, 0, sizeof(fv));
    for (int i = g[r]; i; i = b[i].next)
    {
        for (int j = v; j >= 1; j--)
        {
            for (int k = 1; k <= j; k++)
            {
                fv[j] = max(fv[j], fv[j - k] + f[b[i].to][k]);
            }
        }
    }
    return fv[v];
}

/*
7 4
2 2
0 1
0 4
2 1
7 1
7 6
2 2
*/

/*
10 5
0 4
0 6
1 2
0 1
2 8
4 9
3 7
5 1
8 2
2 4
*/

[左儿子右兄弟]

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#define max(a, b) ((a) > (b) ? (a) : (b))
#define MAXN (300 + 5)
#define INF (6000 + 5)
#define NON (301)
const int root = 0;
using namespace std;
struct node
{
    int left;
    int right;
    int w;
}b[MAXN];
int f[MAXN][MAXN];
int n, m;
int ans;
int dfs(int, int);
void adn(int, int);
void init();
int main()
{
    init();
    ans = dfs(root, m + 1);
    printf("%d", ans);
    return 0;
}

void init()
{
    memset(f, -1, sizeof(f));
    scanf("%d%d", &n, &m);
    int srx, sry;
    for (int i = 0; i <= n; i++)
    {
        b[i].right = b[i].left = NON;
    }
    for (int i = 1; i <= n; i++)
    {    
        scanf("%d%d", &srx, &sry);
        adn(srx, i);
        f[i][0] = 0;
        b[i].w = sry;
    }
    f[NON][0] = 0;
    int bro;
    for (int i = 1; i <= n; i++)
    {
        bro = i;
        int maxw = -INF;
        while (bro != NON)
        {
            maxw = max(maxw, b[bro].w);
            bro = b[bro].right;
        }
        f[i][1] = maxw;
    }
}

void adn(int fr, int to)
{
    if (b[fr].left == NON)
    {
        b[fr].left = to;
    }
    else
    {
        int x = b[fr].left;
        while (b[x].right != NON)
        {
            x = b[x].right;
        }
        b[x].right = to;
    }
}

int dfs(int dq, int dqm)
{    
    if (f[dq][dqm] != -1)
    {
        return f[dq][dqm];
    }
    if (!dqm)
    {
        return f[dq][dqm] = 0;
    }
    if (dq == NON)
    {
        return f[dq][dqm] = -INF;
    }
    /*if (dqm == 1)
    {
        return f[dq][dqm] = max(b[dq].w, dfs(b[dq].right, dqm));
    }*/
    f[dq][dqm] = max(f[dq][dqm], max(dfs(b[dq].right, dqm), dfs(b[dq].left, dqm - 1) + b[dq].w));
    for (int i = 1; i < dqm; i++)
    {
        f[dq][dqm] = max(f[dq][dqm], dfs(b[dq].left, i - 1) + b[dq].w + dfs(b[dq].right, dqm - i));
    }
    return f[dq][dqm] = max(f[dq][dqm], f[b[dq].right][dqm]);
}

/*
7 4
2 2
0 1
0 4
2 1
7 1
7 6
2 2
*/

/*
50 20
0 8
1 6
2 10
0 10
4 10
5 6
3 5
0 10
3 10
0 4
5 8
0 2
6 8
0 10
12 10
10 6
11 5
12 6
12 8
6 8
13 9
13 1
5 8
15 4
16 2
18 2
12 2
21 6
22 4
28 3
24 2
10 9
22 2
24 4
8 5
24 5
8 9
23 6
14 8
36 7
17 7
6 6
12 5
16 8
3 8
27 8
38 9
38 10
42 10
36 5
*/

By 文化课爆炸的 Cansult