我是傻逼

又是被自己菜死的一天，什么时候才能像羽姐姐那么强呀
看题解看一下午都不是很明白，然后发现一直没理解到dp[x][y]代表的是什么，真是菜的真实

思路

dp[x][y]代表以x为根节点这棵树选了y个黑点情况下整棵树(以x为根)的所有白点和黑点相互路径max，所以当对x的父节点q进行计算时，可以背包q的子节点x中选中了y个的最大值，然后采用逆序的遍历方式，这样就能保证不会重复计算，还有一点注意的是可能你剩下的未在分析当前子树的未选择的黑节点个数可能大于所有节点减去这个子树节点个数，这是非法的，因此一开始先设置全部状态为-1，然后当只有一个节点的时候该节点是否为黑节点都是合法的为0，就行了
菜菜菜蔡！！！！！！！！

const int N = 2e3+5;
const int mod1 = 1e9+7;
const int mod9 = 998244353;
int n, k;
vector<PII>edge[N];
int cnt[N];
LL dp[N][N];

void add(int u, int v, int w){
    edge[u].emplace_back(v, w);
}

void dfs(int u, int fa){
    cnt[u] = 1;
    dp[u][0] = 0, dp[u][1] = 0;
    for(auto [v, w] : edge[u]){
        if(v == fa) continue;
        dfs(v, u);
        cnt[u] += cnt[v];
        for(int i = min(k, cnt[u]); i >= 0; --i){
            for(int j = 0; j <= min(i, cnt[v]); ++j){
                if(dp[u][i - j] == -1) continue; 
                LL q = 1LL * w * j * (k - j) + 1LL * (cnt[v] - j) * (n - k - (cnt[v] - j)) * w;
                dp[u][i] = max(dp[u][i], dp[u][i - j] + dp[v][j] + q);
            }
        }
    }
}

void solve(){
    scanf("%d%d", &n, &k);
    for(int i = 1; i < n; ++i){
        int u, v, w; scanf("%d%d%d", &u, &v, &w); 
        add(u, v, w);
        add(v, u, w);
    }
    memset(dp, -1, sizeof dp);
    dfs(1, 0);
    printf("%lld\n", dp[1][k]);
}