其中x为根节点,y为x的子节点
当k=1时,
f[x,0]=sum(max(f[y,0],f[y,1]))
f[x,1]=sum(f[y,0])
========
f[x,0]表示根节点不取,
f[x,1]表示根节点取
========
当根节点取时,子节点全都不能取;
当根节点不取时,子节点可去可不取
当k=2时,
f[x,0]=sum(max(f[y,0],f[y,1]))
f[x,1]=f[x,0]+max(0,max(f[y,2]-max(f[y,0],f[y,1])))
f[x,2]=sum(f[y,0])
========
f[x,0]表示子节点和根节点都不取,
f[x,1]表示根节点不取,子节点取1个,
f[x,2]表示根节点不取
========
当子节点和根节点都不取时,子节点下的子节点可去可不取;
当根节点不取,子节点取1个,个数是在子节点和根节点都不取的基础上再加多一个子节点取的值(或不取,此时f[y,2]-max(f[y,0],f[y,1])<0);
当根节点取时,子节点和它下面的子节点都不能去
======代码如下=========
const maxn=1000000;
type pointer=^node;
node=record
d:longint;
next:pointer;
end;
var n,k,i,x,y:longint;
a:array[1..maxn]of pointer;
f:array[1..maxn,0..2]of longint;
vis:array[1..maxn]of boolean;
p:pointer;
function max(a,b:longint):longint;
begin
if a>b then exit(a)
else exit(b);
end;
procedure dfs1(d:longint);
var i:longint;
p:pointer;
begin
if a[d]=nil then
begin
f[d,0]:=0;
f[d,1]:=1;
end
else begin
p:=a[d];
while p<>nil do
begin
if not(vis[p^.d]) then
begin
vis[p^.d]:=true;
dfs1(p^.d);
inc(f[d,0],max(f[p^.d,1],f[p^.d,0]));
inc(f[d,1],f[p^.d,0]);
end;
p:=p^.next;
end;
inc(f[d,1]);
end;
end;
procedure dfs2(d:longint);
var i,t:longint;
p:pointer;
begin
if a[d]=nil then
begin
f[d,0]:=0;
f[d,1]:=0;
f[d,2]:=1;
end
else begin
p:=a[d];
t:=0;
while p<>nil do
begin
if not(vis[p^.d]) then
begin
vis[p^.d]:=true;
dfs2(p^.d);
inc(f[d,0],max(f[p^.d,0],f[p^.d,1]));
t:=max(t,f[p^.d,2]-max(f[p^.d,0],f[p^.d,1]));
inc(f[d,2],f[p^.d,0]);
end;
p:=p^.next;
end;
inc(f[d,2]);
f[d,1]:=f[d,0]+t;
end;
end;
begin
readln(n,k);
for i:=1 to n-1 do
begin
readln(x,y);
new(p);
p^.d:=y;
p^.next:=a[x];
a[x]:=p;
new(p);
p^.d:=x;
p^.next:=a[y];
a[y]:=p;
end;
case k of
1:
begin
vis[1]:=true;
dfs1(1);
writeln(max(f[1,0],f[1,1]));
end;
2:
begin
vis[1]:=true;
dfs2(1);
writeln(max(max(f[1,0],f[1,1]),f[1,2]));
end;
end;
end.