网站设计的用途,做网站微信朋友圈应该怎么发,h5响应式网站设计方案,佛山网站seo优化排名公司正题
题目链接:https://www.luogu.com.cn/problem/P3177 题目大意 nnn个点的一棵树#xff0c;将kkk个点染成黑色#xff0c;其他是白色#xff0c;使得黑点之间和白点之间两两距离和最大。 解题思路
也是统计每条边的贡献#xff0c;设fx,if_{x,i}fx,i表示节点xxx的子…正题
题目链接:https://www.luogu.com.cn/problem/P3177 题目大意
nnn个点的一棵树将kkk个点染成黑色其他是白色使得黑点之间和白点之间两两距离和最大。 解题思路
也是统计每条边的贡献设fx,if_{x,i}fx,i表示节点xxx的子树中有iii个黑点时的最大子树贡献和。
发现这样转移是O(nk2)O(nk^2)O(nk2)的只要限制iii的枚举范围在sizxsiz_xsizx以内就变成O(n2)O(n^2)O(n2)了原因是节点之间两两做了一次贡献。 codecodecode
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N2100;
struct node{ll to,next,w;
}a[N*2];
ll n,K,tot,ls[N],f[N][N],g[N],siz[N];
void addl(ll x,ll y,ll w){a[tot].toy;a[tot].nextls[x];ls[x]tot;a[tot].ww;return;
}
void dp(ll x,ll fa){siz[x]1;for(ll ils[x];i;ia[i].next){ll ya[i].to;if(yfa)continue;dp(y,x);for(ll j0;jsiz[x];j)g[j]f[x][j],f[x][j]0;for(ll j0;jsiz[x];j)for(ll k0;ksiz[y];k)f[x][jk]max(f[x][jk],g[j]f[y][k]a[i].w*(k*(K-k)(siz[y]-k)*(n-K-siz[y]k))); siz[x]siz[y];}return;
}
int main()
{scanf(%lld%lld,n,K);for(ll i1;in;i){ll x,y,w;scanf(%lld%lld%lld,x,y,w);addl(x,y,w);addl(y,x,w);}dp(1,1);printf(%lld,f[1][K]);
}
