3391: [Usaco2004 Dec]Tree Cutting网络破坏

3391: [Usaco2004 Dec]Tree Cutting网络破坏

Time Limit: 1 Sec  Memory Limit: 128 MB

Submit: 76  Solved: 59

[Submit][Status][Discuss]

Description

    约翰意识到贝茜建设网络花费了他巨额的经费,就把她解雇了.贝茜很愤怒,打算狠狠报

复.她打算破坏刚建成的约翰的网络.    约翰的网络是树形的,连接着N(1≤N≤10000)个牛棚.她打算切断某一个牛棚的电源,使和这个牛棚相连的所有电缆全部中断.之后,就会存在若干子网络.为保证破坏够大,每一个子网的牛棚数不得超过总牛棚数的一半,那哪些牛棚值得破坏呢?

Input

    第1行:一个整数N.

    第2到N+1行:每行输入两个整数,表示一条电缆的两个端点.

Output

    按从小到大的顺序,输出所有值得破坏的牛棚.如果没有一个值得破坏,就输出“NONE”.

Sample Input

10 1 2 2 3 3 4 4 5 6 7 7 8 8 9 9 10 3 8

Sample Output

3 8 如果牛棚3或牛棚8被破坏,剩下的三个子网节点数将是5,2,2,没有超过5的. 来源信息

HINT

Source

Silver

题解:一道树的水题,关键在于如何快速求出各点周围的子树大小,其实只需要DFS预处理出以某点(比如点1)为根的树各个子树的大小,然后对于某一点而言,各子树大小即为在有根树的状况下它的各个子树大小,还有另一个子树大小就是n-size[x](size[x]标是有根树的情形下以x为根的子树的大小),然后简单判断即可,复杂度O(N)

 1 /**************************************************************
 2     Problem: 3391
 3     User: HansBug
 4     Language: Pascal
 5     Result: Accepted
 6     Time:16 ms
 7     Memory:1716 kb
 8 ****************************************************************/
 9  
10 type
11     point=^node;
12     node=record
13                g:longint;
14                next:point;
15     end;
16 var
17    i,j,k,l,m,n:longint;
18    a:array[0..100000] of point;
19    b:array[0..100000] of longint;
20    c:array[0..100000] of longint;
21 procedure add(x,y:longint);
22           var p:point;
23           begin
24                new(p);p^.g:=y;;
25                p^.next:=a[x];a[x]:=p;
26           end;
27 procedure dfs(y,x:longint);
28           var p:point;i:longint;
29           begin
30                p:=a[x];b[x]:=1;i:=1;
31                while p<>nil do
32                      begin
33                           if p^.g<>y then
34                              begin
35                                   dfs(x,p^.g);
36                                   if b[p^.g]>(n div 2) then i:=0;
37                                   inc(b[x],b[p^.g]);
38  
39                              end;
40                           p:=p^.next;
41                      end;
42                if ((n-b[x])<=(n div 2)) and (i=1) then
43                   begin
44                        inc(c[0]);
45                        c[c[0]]:=x;
46                   end;
47           end;
48 procedure sort(l,r:longint);
49           var i,j,x,y:longint;
50           begin
51                i:=l;j:=r;x:=c[(l+r) div 2];
52                repeat
53                      while c[i]<x do inc(i);
54                      while c[j]>x do dec(j);
55                      if i<=j then
56                         begin
57                              y:=c[i];c[i]:=c[j];c[j]:=y;
58                              inc(i);dec(j);
59                         end;
60                until i>j;
61                if i<r then sort(i,r);
62                if l<j then sort(l,j);
63           end;
64 begin
65      readln(n);c[0]:=0;
66      for i:=1 to n do a[i]:=nil;
67      for i:=1 to n-1 do
68          begin
69               readln(j,k);
70               add(j,k);add(k,j);
71          end;
72      dfs(0,1);sort(1,c[0]);
73      for i:=1 to c[0] do writeln(c[i]);
74      readln;
75 end.   

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏一名合格java开发的自我修养

Java IO 装饰者模式

  装饰模式以对客户端透明的方式动态地给一个对象附加上更多的责任。换言之,客户端并不会觉得对象在装饰前和装饰后有什么不同。

892
来自专栏码农阿宇

NopCommerce开源项目中很基础但是很实用的C# Helper方法

刚过了个五一,在杭州到处看房子,不知道杭州最近怎么了,杭州买房的人这么多,房价涨得太厉害,这几年翻倍翻倍地涨,刚过G20,又要亚运会,让我这样的刚需用户买不起,...

42011
来自专栏算法修养

浙江工业大学校赛 小M和天平

小M和天平 Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Ja...

2966
来自专栏aCloudDeveloper

string 之 strlen函数

Author: bakari  Date: 2012/8/9 近两年好多的IT公司喜欢拿一些库函数来考,string函数库当然是首选,除此之外,像qsort,S...

1917
来自专栏Java帮帮-微信公众号-技术文章全总结

【学习经验】Java中常用英文

【学习经验】Java中常用英文 第一章: public['pʌblik] 公共的,公用的 static['stætik] 静的;静态的...

36010
来自专栏小樱的经验随笔

BZOJ 1061: [Noi2008]志愿者招募【单纯形裸题】

1061: [Noi2008]志愿者招募 Time Limit: 20 Sec  Memory Limit: 162 MB Submit: 4813  Solv...

3505
来自专栏lonelydawn的前端猿区

Node.js力破江苏网警刑侦科推理试题

月前,江苏网警 在微博发布了一套《2018年刑侦科目推理试题》,可谓难倒了诸多英雄好汉,评论区内更是一片皮皮之音。 @二向箔icon: 高考前班主任教过我们,...

3087
来自专栏Kurt Niu 的博客

ThoughtWorks 百年不变的面试题之 --- Merchant's Guide To The Galaxy

Code: https://github.com/zifeiniu/Merchants-Guide-To-The-Galaxy

7761
来自专栏码农阿宇

NopCommerce开源项目中很基础但是很实用的C# Helper方法

3793
来自专栏数据结构与算法

BZOJ1061: [Noi2008]志愿者招募(线性规划)

  申奥成功后,布布经过不懈努力,终于成为奥组委下属公司人力资源部门的主管。布布刚上任就遇到了一个难

1294

扫码关注云+社区