《[2017年整理]切割树 treecut ---题意简述》由会员分享，可在线阅读，更多相关《[2017年整理]切割树 treecut ---题意简述（10页珍藏版）》请在金锄头文库上搜索。
1、切割树 treecut -题意简述 有一个N个节点的无根树，各节点编号为 1N，现在要求你删除其中的一个点，使分 割开的连通块中节点个数都不超过原来的 一半。 数据范围 1 0 do begin a:=pp1.v; /相邻点 if c a =0 then begin / if 没有访 问过的 c a :=dfs( a ); /递归 . end; p1:=pp1.next; /取链表下一个 节点 end; end;切割树 treecut -参考程序 function dfs( root : integer) :integer; begin . while p1 N div 2 then okro
2、ot:=false; /a分支节点 过多 inc(croot, c a ); end; p1:=pp1.next; /取链表下一个节点 end; if ( N - croot N div 2 ) then okroot :=false; /向上分 支判断 dfs := croot; end;切割树 treecut -参考程序 begin assign(input, treecut.in); reset(input); assign(output,treecut.out); rewrite(output); init; dfs(1); a:=0; for i:=1 to N do if oki then begin writeln(i); inc(a); end; if a=0 then writeln(NONE); close(output); close(input); end.
