E. Paint the Tree 树形dp

E. Paint the Tree

题目大意：给你一棵树，每一个点都可以染k种颜色，你拥有无数种颜色，每一种颜色最多使用2次，如果一条边的两个节点拥有同一种颜色，那么就说

这条边是饱和的，一个树的价值定义为饱和边的权值之和，问一棵树的最大价值是多少。

dp[u][1] 表示这条边用了k种颜色了。

dp[u][0] 表示这条边用了k-1种颜色。

子节点往父亲节点转移的时候，这个转移带有一点点的贪心。

首先因为每一个子节点到父亲节点的这条边要不要都会对后面产生影响。

所以我们可以构造一个模型，dp模型

如果有n个物品，每一个物品有两种选择，A和B，有一个限制就是如果选A，那么选A的数量不能超过k个，然后问选完之后的最大价值，A的价值为a, B的价值为b。

这个就可以用dp来考虑，dp[i][j] 表示前面 i 个选了j个A的最大价值。

当然也可以不dp，可以贪心的考虑，因为所有的B都是可以选择的，所以我们先考虑，选择所有的B，然后考虑，如果要换成A可以增加的差值。

sort排序找前面k大且大于0的差值。

这个题目也是一样的，我们就先选了所有的dp[v][1] 然后如果选这条边，那么差值就是dp[v][0]+w-dp[v][1]

找前面k大且大于0的数之和。

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <queue>

#include <stack>

#include <bitset>

#include <vector>

#include <map>

#include <string>

#include <cstring>

#include <bitset>

#define inf 0x3f3f3f3f

using namespace std;

const int maxn=5e5+;

typedef long long ll;

ll dp[maxn][];

int n,k,head[maxn],cnt;

struct node{

    int v,w,nxt;

    node(int v=,int w=,int nxt=):v(v),w(w),nxt(nxt){}

}ex[maxn*];

void add(int u,int v,int w){

    ex[cnt]=node(v,w,head[u]);

    head[u]=cnt++;

    ex[cnt]=node(u,w,head[v]);

    head[v]=cnt++;

}

bool cmp(int a,int b){

    return a>b;

}

void dfs(int u,int pre){

    dp[u][]=dp[u][]=;

    for(int i=head[u];i!=-;i=ex[i].nxt){

        int v=ex[i].v;

        if(v==pre) continue;

        dfs(v,u);

        dp[u][]+=dp[v][];

        dp[u][]+=dp[v][];

    }

    vector<int>val;val.clear();

    for(int i=head[u];i!=-;i=ex[i].nxt){

        int v=ex[i].v;

        if(v==pre) continue;

        val.push_back(dp[v][]+ex[i].w-dp[v][]);

    }

    sort(val.begin(),val.end(),cmp);

    int len=val.size();

    len=min(k,len);

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

        if(val[i]<) break;

        if(i<k-) dp[u][]+=val[i];

        dp[u][]+=val[i];

    }

}

int main(){

    int t;

    scanf("%d",&t);

    while(t--){

        cnt=;

        scanf("%d%d",&n,&k);

        for(int i=;i<=n;i++) head[i]=-;

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

            int u,v,w;

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

            add(u,v,w);

        }

        dfs(,-);

        printf("%lld\n",max(dp[][],dp[][]));

    }

    return ;

}

巴特西

E. Paint the Tree 树形dp

最新文章

热门文章