3599: 切割树-训练套题T2T2

n       有一个N个节点的无根树，各节点编号为1..N，现在要求你删除其中的一个点，使分割开的连通块中节点个数都不超过原来的一半。 

n       数据范围    1 <= N <= 10,000

n         数据结构--树的表示： 

n           1) 由于1 <= N <= 10,000，比较大，不适合用 邻接矩阵（?）

n           2)用邻接链表

n        算法 --树的递归处理：

n           DFS

n         分割节点的判断：
各分枝的节点个数都不超过原来的一半

n       不能从每个节点为根，DFS一次。
这样为O(N2)复杂度，超时。

n       如果从任意一节点为根DFS，能否计算出每个节点的各个分枝的节点数呢？

n       如果从任意一节点为根DFS，子树的节点数DFS返回时自然都知道，连向“父节点分支” 的节点数呢？

n       

由于节点总数是一定的=N，知道所有子树的节点数，自然可计算出“父节点分枝”的节点数！
    F[父节点] = N – 1 – ∑F（子节点）

n       type Tnode = record  //数组模拟指针的链表节点

n          v, next :integer;

n       end;

n       var

n          p:array[1..20010] of Tnode;  // 链表节点，无向图要2倍

n          link:array [ 1.. 10010] of integer;  //邻接链表的头“指针”

n          c:array[1..10010 ] of integer;     //以i为根的子树中的节点数为c[i]

n          ok:array[1..10010] of boolean;    //是否为分割点

n          N ,i,a,b, pi: integer;

n       procedure init;

n           procedure ins(var a,b :integer);   begin //b节点插入a的链表中

n               p[pi].v := b;    p[pi].next :=link[a];

n               link[a] := pi;    inc(pi);

n           end;

n        begin

n          readln(N);

n          for i:=1 to N do begin link[i]:=0; c[i]:=0; end;

n          pi:=1;

n          for i:=1 to N-1 do   begin   //读入无向边，插入邻接链表

n             readln(a,b);

n             ins(a,b);      ins(b,a);

n          end;

n        end;

n       function dfs( root : integer) :integer;

n        var         p1 , a :integer;

n        begin

n          c[root]:=1 ;                               //节点计数，也防止向上递归

n          ok[root]:=true;                            //是否可以为分割点

n          p1:= link[ root] ;                            //取链表头节点

n          while p1 <> 0 do     begin   a:=p[p1].v;       //相邻点

n             if c[ a ]=0 then      begin                     // if 没有访问过的

n                  c[ a ]:=dfs( a );                               //递归

n            …….

n             end;

n             p1:=p[p1].next;                          //取链表下一个节点

n           end;

n           ……..

n        end;

n       function dfs( root : integer) :integer;

n       …

n       begin

n          ….

n          while p1 <> 0 do     begin   a:=p[p1].v;

n             if c[ a ]=0 then      begin

n                  c[ a ]:=dfs( a );                    

n            if c[ a ]>N div 2 then ok[root]:=false;    //a分支节点过多

n            inc(c[root], c[ a ] );

n             end;

n             p1:=p[p1].next;                             //取链表下一个节点

n           end;

n           if ( N - c[root] > N div 2 ) then ok[root] :=false; //向上分支判断

n           dfs := c[root]; 

n        end;

n       begin

n           assign(input, 'treecut.in'); reset(input);

n           assign(output,'treecut.out'); rewrite(output);

n           init;

n           dfs(1);

n           a:=0;

n           for i:=1 to N do

n             if ok[i] then  begin writeln(i); inc(a); end;

n           if a=0 then writeln('NONE');

n           close(output); close(input);

n        end.