@Junlier
2018-10-31T19:10:47.000000Z
字数 1618
阅读 2022
题解
阅读体验:https://zybuluo.com/Junlier/note/1327400
原题地址:
BZOJ 4033: [HAOI2015]树上染色题解
洛谷 P3177 [HAOI2015]树上染色
应该各大都有。。。可以多倍经验。。。
一眼树形是吧
因为要选出个黑点,所以知道子树内有多少个黑点,就知道子树外有多少个黑点
那么设dp[now][j]
表示在的子树内选了个黑点对答案的贡献
考虑每条边对答案的贡献进行
枚举已经处理完的子树选出了个,当前处理的子树选出了个
一定有 (是当前节点,是子树节点,是now-qw边
对答案的贡献)
dp[now][j+k]=MAX(dp[now][j+k],dp[now][j]+dp[qw][k]+Val);
那么怎么算出呢,这个不难
Val=k*(K-k)*w+(siz[qw]-k)*(n-K-siz[qw]+k)*w;
子树黑点数×外面黑点数×边权 子树白点数×外面白点数×边权
那么这个题目不就很简单吗。。。然而手写MAX忘记开long long Wa了很久
#include<bits/stdc++.h>
#define il inline
#define rg register
#define ldb double
#define lst long long
#define rgt register int
#define N 2050
#define qw ljl[i].to
using namespace std;
const int Inf=1e9;
il lst MAX(rg lst x,rg lst y){return x>y?x:y;}
il int MIN(rgt x,rgt y){return x<y?x:y;}
il lst read()
{
rg lst s=0,m=0;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')m=1;ch=getchar();}
while( isdigit(ch))s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
return m?-s:s;
}
int n,K,Rt;
int hd[N],siz[N],cnt;
lst dp[N][N];//The MAX contribution of [At now][got j black points]
struct EDGE{int to,nxt,v;}ljl[N<<1];
il void Add(rgt p,rgt q,rgt o){ljl[++cnt]=(EDGE){q,hd[p],o},hd[p]=cnt;}
void Dfs(rgt now,rgt fm)
{
siz[now]=1;
for(rgt i=hd[now],w;i;i=ljl[i].nxt)
{
if(qw==fm)continue;Dfs(qw,now),w=ljl[i].v;
for(rgt j=MIN(siz[now],K);j>=0;--j)
for(rgt k=MIN(siz[qw],K-j);k>=0;--k)
{
rg lst Val=1LL*k*(K-k)*w+1LL*(siz[qw]-k)*(n-K-siz[qw]+k)*w;
//The contribution of the edge-black&white
dp[now][j+k]=MAX(dp[now][j+k],dp[now][j]+dp[qw][k]+Val);
}
siz[now]+=siz[qw];
}
}
int main()
{
n=read(),K=read();
srand(time(NULL)),Rt=rand()%n+1;
for(rgt i=1;i<n;++i)
{
rgt p=read(),q=read(),o=read();
Add(p,q,o),Add(q,p,o);
}Dfs(Rt,0);
printf("%lld\n",dp[Rt][K]);
return 0;
}