BZOJ 4033

传送门

考场上交的30分暴力QAQ…Orz cstdio

Orz ydc

$F_{i,k}$表示以$i$为根的子树中选$k$个黑点的收益

然后在$dfs$过程中直接拿每个节点的子树来更新答案就行了

还是太弱啊QAQ


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
program bzoj_4033;
var f,g:array[0..2000,0..2000]of int64;
l:array[1..4000]of record ed,pre,w:longint; end;
lst,size:array[1..2000]of longint;
n,kk,i,tot,a,b,c:longint;
procedure max(var a:int64;b:int64);
begin
if b>a then a:=b;
end;
function min(a,b:longint):longint;
begin
if a<b then exit(a) else exit(b);
end;
procedure link(a,b,c:longint);
begin
inc(tot);
l[tot].pre:=lst[a];
lst[a]:=tot;
l[tot].ed:=b;
l[tot].w:=c;
end;
procedure dfs(t,fa,w:longint);
var k,i,j:longint;
begin
size[t]:=1;
k:=lst[t];
while k<>0 do
begin
if l[k].ed<>fa then
begin
dfs(l[k].ed,t,l[k].w);
for i:=min(size[t],kk) downto 0 do
for j:=min(size[l[k].ed],kk-i) downto 0 do max(g[t,i+j],g[t,i]+f[l[k].ed,j]);
inc(size[t],size[l[k].ed]);
end;
k:=l[k].pre;
end;
for i:=0 to size[t] do f[t,i]:=g[t,i]+int64(w)*(int64(i)*int64(kk-i)+int64(size[t]-i)*int64(n-kk-size[t]+i));
end;
begin
readln(n,kk);
tot:=0;
for i:=1 to n-1 do
begin
readln(a,b,c);
link(a,b,c);
link(b,a,c);
end;
dfs(1,0,0);
writeln(f[1,kk]);
end.