You are given a weighted tree consisting of 𝑛 vertices. Recall that a tree is a connected graph without cycles. Vertices 𝑢𝑖 and 𝑣𝑖 are connected by an edge with weight 𝑤𝑖.

Let's define the 𝑘-coloring of the tree as an assignment of exactly 𝑘 colors to each vertex, so that each color is used no more than two times. You can assume that you have infinitely many colors available. We say that an edge is saturated in the given 𝑘-coloring if its endpoints share at least one color (i.e. there exists a color that is assigned to both endpoints).

Let's also define the value of a 𝑘-coloring as the sum of weights of saturated edges.

Please calculate the maximum possible value of a 𝑘-coloring of the given tree.

You have to answer 𝑞 independent queries.

链接🔗

「CodeForces 1241E」Paint the Tree

题解

树形DP,因为相邻两个点染色才有贡献。
节点每染一种颜色,表示选了一条边,也就意味着一个点不能选超过k条与之相邻的边
DP[x][1] 表示该点边选满了的价值
DP[x][0] 表示未选满的价值
我们考虑到x时,子树都选好了,先不选与自身链接的边,也就是加上所有DP[v][1](v为子树节点)
然后我们依次考虑,DP[v][0]+E{x,v}这条边的权值(也就是是否与该点连边),如果选该边,则要减去DP[v][1],则与该点连边的贡献为(DP[v][0]+E{x,v}-DP[v][1])

然后贪心选前k个就好

代码

const int maxd = 5e5+10;
typedef long long ll;

vector<P> G[maxd];
vector<ll> a;
ll n,k,dp[maxd][2];
// dp[i][0] 表示选满k边的最大价值
void dfs(ll x,ll fa)
{
//    PLL(x);
//    PN();
    dp[x][0] = dp[x][1] = 0;
    for(auto p:G[x])
    {
        ll v = p.st;
        if(v == fa) continue;
        dfs(v,x);
        dp[x][0] += dp[v][1];
        dp[x][1] += dp[v][1]; //先选满的子树
    }
    //选满的子树,这样当前节点就无法与子树节点连边,因为子树点已经满K个了

    a.clear();
    for(auto p:G[x])
    {
        ll v = p.st;
        if(v == fa) continue;
        a.pb(-(dp[v][0]+ p.nd - dp[v][1]));
        //这里我们枚举每个节点的差值,也就是如果子树不选满,则可选这条边
    }
    sort(all(a)); //贪心选择价格高的

    ll len = min((ll)a.size(),k);
    F(len)
    {
        ll v = -a[i];
        if(v < 0)break;
        if(i<k-1) dp[x][0] += v;
        dp[x][1] += v;
    }
}

int main()
{
//    freopen("a.in","r",stdin);
//    freopen("k.out","w",stdout);
    int t;scanf("%d",&t);
    while(t--)
    {
        RLL(n);RLL(k);
        F(n-1)
        {
            ll a,b,c;
            RLL(a);RLL(b);RLL(c);
            //printf("%lld %lld %lld\n",a,b,c);
            G[a].pb(P(b,c));
            G[b].pb(P(a,c));
        }
//        FOR(1,n)
//        {
//            for(auto p: G[i]) printf("%lld ",p.st);
//            PN();
//        }
        dfs(1ll,-1ll);
        FOR(1,n) G[i].clear();
        PLL(max(dp[1][0],dp[1][1]));
        PN();

    }

    return 0;
}