Codeforces 633F The Chocolate Spree 树形dp

The Chocolate Spree

对拍拍了半天才知道哪里写错了。。

dp[ i ][ j ][ k ]表示在 i 这棵子树中有 j 条链， 是否有链延伸上来。

#include<bits/stdc++.h>

#define LL long long

#define fi first

#define se second

#define mk make_pair

#define PLL pair<LL, LL>

#define PLI pair<LL, int>

#define PII pair<int, int>

#define SZ(x) ((int)x.size())

#define ull unsigned long long

using namespace std;

const int N = 1e5 + ;

const int inf = 0x3f3f3f3f;

const LL INF = 0x3f3f3f3f3f3f3f3f;

const int mod = ;

const double eps = 1e-;

const double PI = acos(-);

int n, a[N];

LL dp[N][][];

vector<int> G[N];

inline bool chkmax(LL &a, LL b) {

    return a < b ? a = b, true : false;

}

void dfs(int u, int fa) {

    LL tmp[][];

    LL gg[][];

    dp[u][][] = ;

    for(int i = ; i < ; i++)

        for(int j = ; j < ; j++)

            tmp[i][j] = -INF;

    tmp[][] = ;

    for(auto& v : G[u]) {

        if(v == fa) continue;

        dfs(v, u);

        memcpy(gg, tmp, sizeof(gg));

        for(int i = ; i <= ; i++) {

            for(int j = ; j <= ; j++) {

                for(int x = ; x <= ; x++) {

                    for(int y = ; y <= ; y++) {

                        if(!i && j || !x && y) continue;

                        if(j + y > ) continue;

                        tmp[i + x][j + y] = max(tmp[i + x][j + y], gg[i][j] + dp[v][x][y]);

                    }

                }

            }

        }

    }

    // dp[1][0]

    chkmax(dp[u][][], tmp[][] + a[u]);

    chkmax(dp[u][][], tmp[][]);

    chkmax(dp[u][][], tmp[][] + a[u]);

    chkmax(dp[u][][], tmp[][] + a[u]);

    // dp[1][1]

    chkmax(dp[u][][], tmp[][] + a[u]);

    chkmax(dp[u][][], tmp[][] + a[u]);

    //dp[2][0]

    chkmax(dp[u][][], tmp[][]);

    chkmax(dp[u][][], tmp[][] + a[u]);

    chkmax(dp[u][][], tmp[][] + a[u]);

    //dp[2][1]

    chkmax(dp[u][][], tmp[][] + a[u]);

    chkmax(dp[u][][], tmp[][] + a[u]);

    chkmax(dp[u][][], tmp[][] + a[u]);

}

int main() {

//    freopen("test.in", "r", stdin);

    scanf("%d", &n);

    for(int i = ; i <= n; i++) G[i].clear();

    for(int i = ; i <= n; i++) scanf("%d", &a[i]);

    for(int i = ; i < n; i++) {

        int u, v; scanf("%d%d", &u, &v);

        G[u].push_back(v);

        G[v].push_back(u);

    }

    for(int i = ; i <= n; i++)

        for(int j = ; j < ; j++)

            for(int k = ; k < ; k++)

                dp[i][j][k] = -INF;

    dfs(, );

    LL ans = ;

    for(int i = ; i <= ; i++)

        for(int j = ; j <= ; j++)

            ans = max(ans, dp[][i][j]);

    printf("%lld\n", ans);

    return ;

}

/*

*/