讨论 / 发题解增RP_rqnoj719
sser_cgb 2013-11-04 17:58:20
点我顶贴 收藏 删除
此题为dfs建树+树形dp

其中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.

#1 wshjz@2013-11-05 20:37:40
回复 删除
为何k=1的情况不能用搜索呢?

感觉应该标记了就可以啊

查看更多回复
提交回复