分析

直接求点与点之间的距离感觉不是很好求，所以我们考虑换一个求法。

瞄了一眼题解

距离跟路径上边的长度有关，所以我们直接来看每一条边的贡献吧（这谁想得到啊）

对于每一条边，它的贡献等于（一边的白点数*另一边的白点数+一边的黑点数*另一边的黑点数）*边权

然后。。。。。我又卡住了。再次瞄题解

对于任意一棵子树，只要知道子树的大小和黑点个数，就可以算出将子树与外界相连的那条边的贡献

所以直接dp[i][j]表示i为根节点的子树中与j个黑色节点的对答案的最大贡献，然后直接树上背包就好了。

注意枚举状态的时候不要枚举到无意义的状态（这个点调了我半天）

代码（压行是信仰）

#include<cstdio>

#include<algorithm>

using namespace std;

const int maxn=;

long long dp[maxn][maxn];

int n,K,ecnt,info[maxn],siz[maxn],inp[maxn],nx[maxn*],v[maxn*],w[maxn*];

void add(int u1,int v1,int w1){nx[++ecnt]=info[u1];info[u1]=ecnt;v[ecnt]=v1;w[ecnt]=w1;}

void dfs(int x,int f)

{

    siz[x]=;

    for(int i=info[x];i;i=nx[i])if(v[i]!=f)

    {

        inp[v[i]]=w[i];dfs(v[i],x);siz[x]+=siz[v[i]];

        for(int j=min(siz[x],K);j>=;j--)

        for(int k=;k<=j&&k<=siz[v[i]];k++)

        if(j-k<=siz[x]-siz[v[i]])dp[x][j]=max(dp[x][j],dp[x][j-k]+dp[v[i]][k]);

    }

    for(int i=;i<=siz[x]&&i<=K;i++)

    dp[x][i]+=1ll*(1ll*i*(K-i)+1ll*(siz[x]-i)*(n-K-siz[x]+i))*inp[x];

}

int main()

{

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

    for(int i=,u1,v1,w1;i<n;i++)

    scanf("%d%d%d",&u1,&v1,&w1),add(u1,v1,w1),add(v1,u1,w1);

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

}

巴特西

【洛谷】P3177 [HAOI2015]树上染色

分析

最新文章

热门文章