匿名ip访问网站受限,网站内容描述,做外贸要看哪些网站好,足球推介网4033: [HAOI2015]树上染色 Time Limit: 10 Sec Memory Limit: 256 MBSubmit: 2437 Solved: 1034[Submit][Status][Discuss]Description 有一棵点数为N的树#xff0c;树边有边权。给你一个在0~N之内的正整数K#xff0c;你要在这棵树中选择K个点#xff0c;将其染成黑色树边有边权。给你一个在0~N之内的正整数K你要在这棵树中选择K个点将其染成黑色并 将其他的N-K个点染成白色。将所有点染色后你会获得黑点两两之间的距离加上白点两两之间距离的和的收益。 问收益最大值是多少。 Input 第一行两个整数N,K。 接下来N-1行每行三个正整数fr,to,dis表示该树中存在一条长度为dis的边(fr,to)。 输入保证所有点之间是联通的。 N2000,0KN Output 输出一个正整数表示收益的最大值。 Sample Input 5 2 1 2 3 1 5 1 2 3 1 2 4 2 Sample Output 17 【样例解释】 将点1,2染黑就能获得最大收益。 HINT 2017.9.12新加数据一组 By GXZlegend Source 鸣谢bhiaibogf提供 [Submit][Status][Discuss] 初看此题树上背包f[i][j]表示以i为根的子树选j个黑点的最大收益 然后就发现转移爆炸。 于是令f[i][j]表示以i为根的子树选j个黑点的贡献合并子树贡献后将自己到父亲的边的贡献加上即可转移一句话。 然后就没了 回头一看发现复杂度是$O(n^3)$的于是分析一波复杂度。 $T(n)\sum_{u1}^{n}\sum_{v,w\ is\ a\ son\ of\ u} size[v]\times size[w]\sum_{u1}^{n}\sum_{u\ is\ the\ LCA\ of\ v,w} 1O(n^2)$ 于是就可做了当然如果写丑了还是会变成$O(n^3)$的。 最后要记得边长是long long狂WA不止。 1 #includecstdio2 #includecstring3 #includealgorithm4 #define rep(i,l,r) for (int il; ir; i)5 #define For(i,x) for (int ih[x],k; i; inxt[i])6 typedef long long ll;7 using namespace std;8 9 const int N2010;
10 int n,m,u,v,w,cnt,h[N],sz[N],to[N1],nxt[N1];
11 ll f[N][N],dep[N],val[N1];
12 void add(int u,int v,int w){ to[cnt]v; val[cnt]w; nxt[cnt]h[u]; h[u]cnt; }
13
14 void dfs(int x,int fa){
15 f[x][0]f[x][1]0; sz[x]1;
16 For(i,x) if ((kto[i])!fa){
17 dep[k]val[i]; dfs(k,x);
18 for (int lmin(sz[x],m); l0; l--)
19 for (int jmin(sz[k],m-l); j0; j--) f[x][jl]max(f[x][jl],f[x][l]f[k][j]);
20 sz[x]sz[k];
21 }
22 rep(i,0,min(sz[x],m)) f[x][i]dep[x]*(i*(m-i)(sz[x]-i)*(n-sz[x]-mi));
23 }
24
25 int main(){
26 freopen(bzoj4033.in,r,stdin);
27 freopen(bzoj4033.out,w,stdout);
28 scanf(%d%d,n,m);
29 memset(f,-0x3f,sizeof(f));
30 rep(i,2,n) scanf(%d%d%d,u,v,w),add(u,v,w),add(v,u,w);
31 dfs(1,0); printf(%lld\n,f[1][m]);
32 return 0;
33 } 转载于:https://www.cnblogs.com/HocRiser/p/8757555.html
