一、思路+做法

题目本质：在树上选 k 个黑点，最大化所有边的贡献之和。

核心观察：

• 对任意一条边，它把树分成两部分
• 若左侧有 a 个黑点、b 个白点，右侧有 k-a 个黑点、(n-k)-b 个白点
• 该边贡献 = (左侧黑点数 × 右侧黑点数 + 左侧白点数 × 右侧白点数) × 边权
• 即：[a × (k-a) + b × ((n-k)-b)] × w

DP 设计：

• dp[x][i]：在 x 的子树中选 i 个黑点的最大贡献
• 树上背包合并：把每个子树的方案看成一个"物品组"，类似分组背包
• 合并时，加上当前边 (x,y) 的贡献

做法步骤：

1. 以 1 为根 DFS
2. 对每个节点 x，初始化 dp[x][0]=dp[x][1]=0
3. 逐个合并子节点 y：
   • 枚举 x 子树已选黑点数 i
   • 枚举 y 子树选黑点数 j
   • 计算边 (x,y) 的贡献并更新 dp
4. 最终 dp[1][k] 即为答案

二、代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=5100,M=-1;                    // M 为极小值，表示不可达状态
vector<pair<int,int>>G[N];                  // 邻接表，存 {子节点, 边权}
int dp[N][N],siz[N],tmp[N],n,k;             // dp[i][j]: i子树内选j个黑点的最大收益

void dfs(int x,int fa)
{
    siz[x]=1;                               // 初始化子树大小为1（仅自己）
    dp[x][0]=dp[x][1]=0;                    // 选0个或1个黑点（自己染黑）基础收益为0
    
    for(auto i:G[x])if(i.first!=fa)         // 遍历所有子节点（排除父节点）
    {
        int y=i.first,w=i.second;           // y是子节点，w是边权
        dfs(y,x);                           // 先递归处理子节点y
        
        memset(tmp,-1,sizeof tmp);           // 清空临时数组
        for(int i=0;i<=siz[x]+siz[y];i++)tmp[i]=M;  // 初始化为极小值
        
        for(int i=0;i<=siz[x];i++)          // 枚举x子树（不含y）已选的黑点数
        {
            if(dp[x][i]<0)continue;         // dp[x][i]为负表示该状态不可达，跳过
            for(int j=0;j<=siz[y];j++)      // 枚举y子树中选的黑点数
            {
                if(dp[y][j]<0)continue;     // dp[y][j]为负表示该状态不可达，跳过
                
                // 计算边(x,y)的贡献：
                // 左侧黑点数 j，右侧黑点数 k-j
                // 左侧白点数 siz[y]-j，右侧白点数 (n-k)-(siz[y]-j)
                int cnt=j*(k-j)+(siz[y]-j)*((n-k)-(siz[y]-j));
                
                // 合并：总收益 = x子树收益 + y子树收益 + 边的贡献
                int val=dp[x][i]+dp[y][j]+cnt*w;
                tmp[i+j]=max(tmp[i+j],val); // 用更优值更新
            }
        }
        
        siz[x]+=siz[y];                     // 更新x的子树大小（加入了y）
        for(int i=0;i<=siz[x];i++)dp[x][i]=tmp[i];  // 将临时结果复制回dp
    }
}

signed main()
{
    cin>>n>>k;
    for(int i=1,x,y,w;i<n;i++)              // 读入n-1条边
    {
        cin>>x>>y>>w;
        G[x].push_back({y,w});              // 无向图，双向存边
        G[y].push_back({x,w});
    }
    
    for(int i=0;i<=n+1;i++)for(int j=0;j<=n+1;j++)dp[i][j]=M;  // 全部初始化为极小值
    
    dfs(1,0);                               // 从根节点1开始DFS
    cout<<dp[1][k];                         // 输出根节点子树选k个黑点的最大收益
    return 0;
}

三、分析

1. 状态设计

dp[x][i] 表示以 x 为根的子树中，恰好选 i 个黑点的最大收益。这里的"收益"指子树内部所有边的贡献之和。

2. 初始化

• dp[x][0]=0：不选黑点，收益为0
• dp[x][1]=0：只把自己染黑，子树内没有边，收益为0
• 其余状态初始化为 M=-1（极小值），表示不可达

3. 合并过程（树上背包）

把每个子节点 y 看作一个"物品组"，其中包含 siz[y]+1 种选择（选0~siz[y]个黑点）。合并时：

• 枚举当前已处理部分（x和已合并的子节点）的黑点数 i
• 枚举新子节点 y 中的黑点数 j
• 转移时加上边 (x,y) 的贡献

4. 边贡献的计算

边 (x,y) 把树分成两部分（y侧 和 其余部分）：

• y侧：黑点 j 个，白点 siz[y]-j 个
• 其余侧：黑点 k-j 个，白点 (n-k)-(siz[y]-j) 个
• 贡献 = [j × (k-j) + (siz[y]-j) × ((n-k)-(siz[y]-j))] × w

5. 复杂度

• 每个节点合并一次，合并时枚举 i 和 j，时间复杂度 O(n²)

6. 正确性证明

• 子问题独立：每个子树内部的最优解不会受外部影响，只需知道子树的黑点数
• 最优子结构：子树的最优解可组合成全局最优解
• 边贡献在合并时计算，保证每条边恰好被计算一次

四、易错点

1. tmp 数组大小：应为 siz[x]+siz[y]，因为合并后最多选这么多黑点
2. 跳过不可达状态：dp[x][i]<0 时跳过，防止错误转移
3. dp[x][1]=0：自己染黑但没有子节点时，边贡献为0。
4. 根节点选择：以1为根，最终答案 dp[1][k] 包含所有边

E73 树形DP P3177 [HAOI2015] 树上染色

// 树形DP O(n^2)
#include <iostream>
#include <cstring>
#include <algorithm>
#define LL long long
using namespace std;

const int N=2005;
int idx,head[N];
struct E{int v,ne;LL w;}e[N<<1];
void add(int u,int v,int w){
  e[++idx]={v,head[u],w};head[u]=idx;
}
int n,m,siz[N];
LL f[N][N],t;

void dfs(int u,int fa){
  siz[u]=1;
  for(int i=head[u];i;i=e[i].ne){
    int v=e[i].v; LL w=e[i].w;
    if(v==fa) continue;
    dfs(v,u);
    for(int j=min(siz[u],m);j>=0;--j)
      for(int k=min(siz[v],m);k>=0;--k)
      if(j+k<=m){
        t=k*(m-k)*w+(siz[v]-k)*(n-siz[v]-m+k)*w;
        f[u][j+k]=max(f[u][j+k],f[u][j]+f[v][k]+t);
      }
    siz[u]+=siz[v];
  }
}
int main(){
  scanf("%d%d",&n,&m);
  for(int i=1,u,v,w;i<n;++i){
    scanf("%d%d%d",&u,&v,&w);
    add(u,v,w), add(v,u,w);
  }
  dfs(1,0);
  printf("%lld\n",f[1][m]);
}