Jumanji 16/17 D

#include <iostream>
#include <algorithm>
#include <fstream>
#include <vector>
#include <queue>
#include <functional>
#include <set>
#include <map>
#include <math.h>
#include <cmath>
#include <string>
#include <time.h>
#include <random>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <string.h>
#include <stack>
using namespace std;
//
#define fast cin.tie(0);cout.tie(0);cin.sync_with_stdio(0);cout.sync_with_stdio(0);
#define cin in
#define cout out
#define ll long long
#define db double
#define ld long double
#define uset unordered_set
#define umap unordered_map
#define F first
#define S second
#define vec vector
#define ms multiset
#define pb push_back
#define pdd pair<ld, ld>
#define pq priority_queue
#define umap unordered_map
#define uset unordered_set
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pnn pair<Node*, Node*>
#define uid uniform_int_distribution
#define ull unsigned long long

ifstream in("input.txt");
ofstream out("output.txt");

const ll INF = 1e18;
const int MAX_N = 1000;
int sz[MAX_N], c[MAX_N];
vector<int> g[MAX_N];
int n, k;
ll dp[MAX_N][MAX_N + 1][2];

void dfs(int v, int p) {
    sz[v] = 1;

    vector<vector<ll>> cdp0(1, vector<ll>(2 * k + 1, -INF));//not in path
    vector<vector<ll>> cdp1(1, vector<ll>(2 * k + 1, -INF));//end of path
    vector<vector<ll>> cdp2(1, vector<ll>(2 * k + 1, -INF));//not end of path
    cdp0[0][0] = 0;
    int p = 0;

    for (int to : g[v]) {
        if (to == p) continue;

        dfs(to, v);
        p++;

        cdp0.push_back(vector<ll>(2 * k + 1, -INF));
        cdp1.push_back(vector<ll>(2 * k + 1, -INF));
        cdp2.push_back(vector<ll>(2 * k + 1, -INF));

        for (int i = 0; i <= k && i <= sz[v]; i++) {
            for (int j = 0; j <= k && j <= sz[to]; j++) {

                //0 + 0
                if(i + j <= k && cdp0[p-1][i] != -INF && dp[to][j][0] != -INF)
                    cdp0[p][i + j] = max(cdp0[p][i + j], cdp0[p - 1][i] + dp[to][j][0]);

                //0 + 1, don't add u
                if (i + j <= k && cdp0[p-1][i] != -INF && dp[to][j][1] != -INF)
                    cdp0[p][i + j] = max(cdp0[p][i + j], cdp0[p - 1][i] + dp[to][j][1]);

                //0 + 1, add u
                if(i + j <= k && cdp0[p-1][i] != -INF && dp[to][j][1] != -INF)
                    cdp1[p][i + j] = max(cdp1[p][i + j], cdp0[p - 1][i] + dp[to][j][1] + c[v]);

                //1 + 0
                if(i + j <= k && cdp1[p - 1][i] != -INF && dp[to][j][0] != -INF)
                    cdp1[p][i + j] = max(cdp1[p][i + j], cdp1[p - 1][i] + dp[to][j][0]);

                //1 + 1, don't merge
                if(i + j <= k && cdp1[p - 1][i] != -INF && dp[to][j][1] != -INF)
                    cdp1[p][i + j] = max(cdp1[p][i + j], cdp1[p - 1][i] + dp[to][j][1]);

                //1 + 1, merge
                if(i + j - 1 <= k && i + j - 1 >= 0 && cdp1[p - 1][i] != -INF && dp[to][j][1] != -INF)
                    cdp2[p][i + j - 1] = max(cdp2[p][i + j - 1], cdp1[p - 1][i] + dp[to][j][1]);

                //2 + 0
                if(i + j <= k && cdp2[p - 1][i] != -INF && dp[to][j][0] != -INF)
                    cdp2[p][i + j] = max(cdp2[p][i + j], cdp2[p - 1][i] + dp[to][j][0]);

                //2 + 1
                if(i + j <= k && cdp2[p - 1][i] != -INF && dp[to][j][1] != -INF)
                    cdp2[p][i + j] = max(cdp2[p][i + j], cdp2[p - 1][i] + dp[to][j][1]);
            }
        }

        sz[v] += sz[to];

    }
}

int main() {
    fast;


}