BZOJ

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.