f[i][j]表示以i为根 选择的节点与i的距离中最近的至少为j的子树的 权值和最大值
(注意是至少为j,就是说可以比j大,也就是说f[i][j]包含f[i][j+1]的情况 也就是有f[i][j]>=f[i][j+1])
当j>k/2(取下整) f[i][j]=max(sigma(f[s][j-1]),f[i][j+1]) (s为i儿子)
当k/2(取下整)>=j>0 f[i][j]=max(sigma(f[s][k-j-1])-f[k][k-j-1]+f[k][j-1],f[i][j+1]) (s为i儿子 k为i某一儿子) (因为如果有两个儿子都距i小于k/2 则两儿子之间距离小于k)
当j=0 f[i][j]=max(sigma(f[s][k-1]),f[i][j+1])
上面方程有的地方取上整 取下整有点问题,然后加减1也有可能有问题,稍微想一下,分情况讨论就清楚了
反正转移方程差不多是这样,sigma可以处理一下就是n^2的了
感谢神牛。
附代码：
var
i,j,tot,x,y,n,k:longint;
v:array[1..100000] of boolean;
f,tmp,q:array[1..100000,0..102] of longint;
a:array[1..300001,1..2] of longint;
w:array[1..100000] of longint;
procedure dfs(k1:longint);
var
i,j,x,y:longint;
begin
v[k1]:=true;
x:=k1;
while a[x,2]<>0 do
begin
y:=a[a[x,2],1];
if not v[y] then
begin
dfs(y);
for i:=0 to k do tmp[k1,i]:=tmp[k1,i]+f[y,i];
for i:=0 to k-2 do
if f[y,i]-f[y,k-i-2]>q[k1,i] then
q[k1,i]:=f[y,i]-f[y,k-i-2];
end;
x:=a[x,2];
end;
for i:=k downto 0 do
begin
if i>=(k+1) div 2 then
begin
if tmp[k1,i-1]>f[k1,i+1] then
f[k1,i]:=tmp[k1,i-1]
else f[k1,i]:=f[k1,i+1];
end
else if i=0 then
begin
if tmp[k1,k-1]+w[k1]>f[k1,i+1] then
f[k1,i]:=tmp[k1,k-1]+w[k1]
else f[k1,i]:=f[k1,i+1];
end
else if i<(k+1) div 2 then
begin
if tmp[k1,k-i-1]+q[k1,i-1]>f[k1,i+1] then
f[k1,i]:=tmp[k1,k-i-1]+q[k1,i-1]
else f[k1,i]:=f[k1,i+1];
end;
end;
end;
begin
readln(n,k);
inc(k);
for i:=1 to n do
read(w[i]);
tot:=n;
for i:=1 to n-1 do
begin
readln(x,y);
inc(tot); a[tot,1]:=y; a[tot,2]:=a[x,2]; a[x,2]:=tot;
inc(tot); a[tot,1]:=x; a[tot,2]:=a[y,2]; a[y,2]:=tot;
end;
dfs(1);
writeln(f[1,0]);
end.