牛客多校Round 2

Solved:3

rank:187

H.travel

题意:给一颗带有点权的树找三条不相交的链使得点权最大

题解:使用树形DP dp[x][i][0/1] 表示x节点选择i条链有没有经过x的链

　　对于每一个回溯的状态下面的结点已经处理好了

　　但是处理当前结点时还有一种有两条经过x的链实际上他们可以合成一条链

　　为了避免重复计算经过当前结点的权值在更新时计算

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n;

ll val[];

ll dp[][][];

vector<int> g[];

void dfs(int x, int fa)

{

    ll tmp[][]; ll f[][];

    for(int i = ; i < ; i++) tmp[i][] = tmp[i][] = tmp[i][] = ;

    for(int i = ; i < g[x].size(); i++)

    {

        int v = g[x][i];

        if(v == fa) continue;

        dfs(v, x);

        memcpy(f, tmp, sizeof(tmp));

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

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

            {

                if(a + b > ) continue;

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

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

                    {

                        if(c + d > ) continue;

                        tmp[a + b][c + d] = max(tmp[a + b][c + d], f[a][c] + dp[v][b][d]);

                    }

            }

    }

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

    {

        dp[x][i][] = max(dp[x][i][], tmp[i][]);

        dp[x][i][] = max(dp[x][i][], tmp[i][] + val[x]);

        if(i < )

        {

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

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

                    dp[x][i + ][j] = max(dp[x][i + ][j], tmp[i][k] + val[x]);

        }

    }

}

int main()

{

    scanf("%d", &n);

    for(int i = ; i <= n; i++) scanf("%lld", &val[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);

    }

    dfs(, -);

    ll ans = ;

    for(int i = ; i < ; i++) ans = max(ans, dp[][i][]);

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

    return ;

}

/*

13

10 10 10 10 10 1 10 10 10 1 10 10 10

1 2

2 3

3 4

4 5

2 6

6 7

7 8

7 9

6 10

10 11

11 12

11 13

*/

巴特西

牛客多校Round 2

最新文章

热门文章