libreoj #10153 树形dp

$des$

有一棵二叉苹果树，如果数字有分叉，一定是分两叉，即没有只有一个儿子的节点。这棵树共 NNN 个节点，标号 1 至 N，树根编号一定为 1。

我们用一根树枝两端连接的节点编号描述一根树枝的位置。一棵有四根树枝的苹果树，因为树枝太多了，需要剪枝。但是一些树枝上长有苹果，给定需要保留的树枝数量，求最多能留住多少苹果

$sol$

树形dp

$f_{i, j}$ 表示以 $i$ 为根的子树中保留 $j$ 个的最大值

转移时枚举该子树保留了多少以及两个儿子分别保留了多少

#include <bits/stdc++.h>

using namespace std;

#define Rep(i, a, b) for(int i = a; i <= b; i ++)

const int N = ;

vector <pair <int, int> > G[N];

int n, Q;

int f[N][N];

void Dfs(int u, int fa) {

    int S = G[u].size();

    int v1 = -, w1, v2 = -, w2;

    Rep(i, , S - ) {

        pair<int, int> P = G[u][i];

        if(P.first == fa) continue;

        if(v1 == -) v1 = P.first, w1 = P.second;

        else v2 = P.first, w2 = P.second;

        if(v1 == - || v2 == -) continue;

        Dfs(v1, u);

        Dfs(v2, u);

        Rep(q, , Q) {

            Rep(l, , q) {

                int r = q - l;

                if(l == ) f[u][q] = max(f[u][q], f[v2][r - ] + w2);

                else if(r == ) f[u][q] = max(f[u][q], f[v1][l - ] + w1);

                else f[u][q] = max(f[u][q], f[v1][l - ] + w1 + f[v2][r - ] + w2);

            }

        }

    }

}

int main() {

    cin >> n >> Q;

    Rep(i, , n - ) {

        int u, v, w; cin >> u >> v >> w;

        G[u].push_back(make_pair(v, w));

        G[v].push_back(make_pair(u, w));

    }

    Dfs(, );

    cout << f[][Q];

    return ;

}

巴特西

libreoj #10153 树形dp

最新文章

热门文章