「HAOI2015树上染色」「树形DP」

其实我还不大会树形DP

此题就当练手叭，缕一下思路就好

题目链接 BZOJ4033

题目大意就是给一棵树，对一部分点染成黑色，剩下的为白色，问所有同色点距离之和。。。。。。。

简明扼要的题意，然额我不会QAQ

大概意思是要，枚举父亲节点分给字节点黑点k的个数，然后

子树内的白点数*树外的白点数*边权+子树内黑点数*子树外黑点数*边权

的最大值即答案

#include <iostream>

#include <algorithm>

#include <cstdio>

#include <vector>

#include <cmath>

#define int long long

using namespace std;

int n,kk;

const int maxn=;

int f[maxn][maxn],size[maxn];//f数组即dp，f[i][j]表示当前节点i下放j个黑点时对答案的最大贡献

vector<pair<int,int> >G[maxn];//first表示下一个子节点，second表示边权

inline void dfs(int x,int fa){

    f[x][]=f[x][]=;//当前一个点也没有，初值为零

    int u;//字节点

    int ans;

    size[x]=;

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

        u=G[x][i].first;//枚举所有孩子

        if(u==fa) continue;

        dfs(u,x);

        size[x]+=size[u];//权值统计

        for(int j=size[x];j>=;j--){//要倒着循环

            for(int k=;k<=size[u]&&k<=j;k++){//j-k的个数

                ans=k*(kk-k)+(size[u]-k)*(n-kk-(size[u]-k));//先加起来

                ans*=G[x][i].second;//乘上边权

                ans+=f[u][k];//统计答案

                f[x][j]=max(f[x][j],f[x][j-k]+ans);//背包

            }

        }

    }

}

signed main(){

    cin>>n>>kk;

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

        int x,y,z;

        cin>>x>>y>>z;

        G[x].push_back(make_pair(y,z));

        G[y].push_back(make_pair(x,z));

    }//建图

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

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

            f[i][j]=-0x7ffffffffffffff;//因为要取max，初始化为极小值

    dfs(,);

    cout<<f[][kk]<<'\n';//以1为根节点，选取kk个黑点的最大贡献即答案

    return ;

}