传染病控制(200分)

已知某种传染病的传播途径是一棵树，其中根节点为1，是已经被感染的患者。病毒在一个传染周期内，只会感染下一代患者；而疾控中心在一个传染周期内，也只能切断一条传染路径。请针对给定的树，找出合适的切断序列，使被感染的总人数最少。
输入格式
第一行是1个整数N，为该树的节点数。N<=300。接下来N-1行，每行两个整数I、J，表示I和J之间存在传染路径。
输出最少感染的总人数。
例如
7
1 2
1 3
4 2
2 5
3 6
3 7
输出
3

该问题即为找出这棵树中高度最短的叶子结点，输出其高度
问题的求解思路为：
1.读入所给数据
2.根据所给数据构造树型结构
3.计算高度最短的叶子结点的高度
4.输出
第3步的递归算法如下：
if(root=NULL) return 0;
else
{
求左孩子的高度;
求右孩子的高度;
if(左孩子的高度 > 右孩子的高度) result:=右孩子的高度+1;
else
result:=左孩子的高度+1;
}

楼上的读错题了，这个问题没有这么简单

既然你知道意思，怎么不解释一下

对于除根节点外的每一层节点，你可以选择去掉一个。去掉该节点之后，该节点的子树也被去掉。而其余节点则被感染。如此重复到最后一层。要求使被感染的节点数最少。

给大家一组数据
输入
200
2 1
3 2
4 3
5 4
6 4
7 4
8 3
9 3
10 9
11 9
12 11
13 11
14 9
15 9
16 2
17 16
18 17
19 17
20 16
21 20
22 16
23 22
24 2
25 24
26 25
27 24
28 27
29 27
30 27
31 2
32 31
33 32
34 32
35 32
36 35
37 35
38 32
39 31
40 39
41 40
42 40
43 40
44 39
45 44
46 1
47 46
48 47
49 48
50 49
51 49
52 49
53 48
54 53
55 47
56 55
57 55
58 57
59 47
60 59
61 60
62 59
63 62
64 46
65 64
66 65
67 65
68 67
69 64
70 69
71 69
72 64
73 72
74 72
75 64
76 75
77 75
78 46
79 78
80 79
81 80
82 81
83 80
84 80
85 84
86 79
87 86
88 86
89 78
90 89
91 90
92 90
93 89
94 93
95 89
96 95
97 1
98 97
99 98
100 99
101 98
102 101
103 98
104 98
105 104
106 104
107 106
108 97
109 108
110 109
111 109
112 111
113 109
114 108
115 114
116 115
117 114
118 114
119 118
120 118
121 108
122 121
123 97
124 123
125 124
126 125
127 124
128 127
129 127
130 127
131 127
132 123
133 132
134 133
135 134
136 133
137 133
138 137
139 137
140 132
141 140
142 140
143 97
144 143
145 144
146 144
147 146
148 144
149 148
150 143
151 150
152 150
153 1
154 153
155 154
156 155
157 156
158 155
159 158
160 158
161 155
162 161
163 161
164 154
165 164
166 165
167 164
168 167
169 164
170 169
171 153
172 171
173 171
174 173
175 174
176 173
177 176
178 171
179 178
180 178
181 171
182 181
183 181
184 181
185 181
186 153
187 186
188 187
189 188
190 187
191 187
192 186
193 192
194 192
195 192
196 186
197 196
198 196
199 198
200 196
输出
111

先遍历根节点下的子树，找出节点数最多的子树，断其连接。
然后以余下的节点为根节点，递归调用上面的算法。
最后得到需要的树。
遍历，得到节点数。。。

>>来自：coolfish3000, 时间：2003-12-3 9:30:00, ID：2330138
先遍历根节点下的子树，找出节点数最多的子树，断其连接。
然后以余下的节点为根节点，递归调用上面的算法。
最后得到需要的树。
遍历，得到节点数。。。
好象不完全是這樣。
比如第一層有兩棵子樹，一個9，一個10。
可是不一定斷10是最好的。如果9的那棵樹在第二層分枝非常的多。極端點一個根帶8個葉(一共9個)。而10那棵樹一個根帶一個葉與一棵8個結點的子樹。
很顯然這時在第一輪斷9是明智的。
斷的的時候還要考慮子樹的分枝情況。

对，简单的贪心应该是不对的，不然你试试我给的第二组测试数据就知道了

真的非常不妥也。。。
是不是在同一层的节点中还可以有不同层的节点来感染呢？？？
那段的时候还得考虑到从根节点到最后一层节点的最短路径，看是否满足要求。。。

需要认真考虑

to coolfish3000:因为题目已经说明了是树，而且是根节点1被感染，所以被感染的节点在一个传染周期内只会传染下一层节点

好象得從葉子往上溯來做。先對每一個節點標記
把我舉的那個樹。改一下，10那棵子樹改為11個節點的樹，一根帶2葉與8節點的子樹
葉子記為0。表示不會感染到任何人。
對11個點的那棵樹的根來講先找它的所有子的標記的最大值。
應該是那棵子樹的根標記值最大了。然後把其余結點的標記值+1後相加，那這棵樹的根的標記值就是2了。表示到了這一層後最少感染人數是2人。
如此這般，那棵9節點的樹的根的標記值是7。
由這兩棵樹組成的樹的根的標記是3。
由此往上走就是了。
上到最頂後。又往下一路找最小的標記值的子就是，那個子的孫中最大的就是應該斷掉的。
沒法畫圖，不知說得清楚不，大概就是這個意思。

贪心方法之一，不能保证全对
如果你觉得可以保证，请从理论上证明，或者贴出程序

to lichdr:
能不能说清楚点，能贴个程序吗???好研究一下。。。

程序沒空寫，看明天有空不。
從底往上走。先保證各個子結點的最少感染人數。就是如果不切掉它後面它會造成感染多少(不包括自身)。
我舉的那個例子。
11個節點的那棵子對的標記值為2。表示如果不切掉它後面它會有2人被感染。
而9個節點的那棵值為7，不切掉它後面會有7人。
這兩個子樹組成的樹的值為3，最後感染人數應該是4(加上根)。如果這棵樹作為人家的子樹道理一樣了。
感染人數在從葉開始標記值到根結束後就可確定了。感染人數=根的值+1。
標記完後。這時切斷的依據不是它的樹的節點數了，而是成了那個標記值了。

好复杂啊

to lichdr:这个方法我也想过，但是不对。不信你自己画个稍微复杂一点的树（当然不要像我给的第二个数据那么复杂），就可以看出问题。你的确可以保证子树感染人数最少，但是对于深度相同的多个子树，你却不能保证每颗子树都能达到最小值，因为同一个深度你只能剪一次，而不是对每颗子树都能剪一次。我还想过保存最多和最少，似乎还是不行。

那天想糊塗了，的確有問題。
靠這樣想也想不出來，回頭去看看圖論的書再回來說了。

某个强人用最小树形图贪心，十个测试点全过。不过我到现在还没想通他是怎么贪的。