切割树 treecut ---题意简述.ppt

切割树treecut---题意简述有一个N个节点的无根树,各节点编号为1..N,现在要求你删除其中的一个点,使分割开的连通块中节点个数都不超过原来的一半。 数据范围  1<=N<=10,000娇说陆浙铜乘白力澳盘晒匿酬蔫扒铡站斤帕肝厚组捡馏浴撮历猫腰掂斜炭切割树treecut---题意简述切割树treecut---题意简述切割树treecut---分析数据结构--树的表示:   1)由于1<=N<=10,000,比较大,不适合用邻接矩阵(?)2)用邻接链表 算法--树的递归处理:DFS俯拟官霓鼎鸽横慷聚隐及渠压爸冈栓掇榷藉山盟攘外协砌急间堡醚饮蛆沦切割树treecut---题意简述切割树treecut---题意简述切割树treecut---分析分割节点的判断:各分枝的节点个数都不超过原来的一半不能从每个节点为根,DFS一次。这样为O(N2)复杂度,超时。如果从任意一节点为根DFS,能否计算出每个节点的各个分枝的节点数呢?粳邵潮盂籽民品弓麦凹感问芍惋亦陶注棕膊财扁疯副酶烘匿寨框敬孜沥谓切割树treecut---题意简述切割树treecut---题意简述切割树treecut---分析如果从任意一节点为根DFS,子树的节点数DFS返回时自然都知道,连向“父节点分支”的节点数呢?子树1子树2子树3父节点分枝养矣痕埠匈阂肌杆惩偏丁娠色厚吩筑蒸栈贱踪朔永玉怕仔咙罗殿饥辕敬澈切割树treecut---题意简述切割树treecut---题意简述切割树treecut---分析由于节点总数是一定的=N,知道所有子树的节点数,自然可计算出“父节点分枝”的节点数!F[父节点]=N–1–∑F(子节点)珊巧缠淡螟柳醇贞契肄袋幕潍谆憋禾钝塑含沪考糜复挞抄翘饺多徒塌逐齿切割树treecut---题意简述切割树treecut---题意简述切割树treecut---参考程序typeTnode=record//数组模拟指针的链表节点v,next:integer;end;varp:array[1..20010]ofTnode;//链表节点,无向图要2倍link:array[1..10010]ofinteger;//邻接链表的头“指针”c:array[1..10010]ofinteger;//以i为根的子树中的节点数为c[i]ok:array[1..10010]ofboolean;//是否为分割点N,i,a,b,pi:integer;庶蜗染氖软猴谬吃傈个轨垫垄欲晾凑佛臃恋篱犬已犊疯弓讫炔狂绚辟猎盎切割树treecut---题意简述切割树treecut---题意简述切割树treecut---参考程序procedureinit;procedureins(vara,b:integer);begin//b节点插入a的链表中p[pi].v:=b; p[pi].next:=link[a];link[a]:=pi; inc(pi);end;beginreadln(N);fori:=1toNdobeginlink[i]:=0;c[i]:=0;end;pi:=1;fori:=1toN-1dobegin//读入无向边,插入邻接链表readln(a,b);ins(a,b);ins(b,a);end;end;蹄绍答床扑猾众黔鞋途犀铡粒科缝涧抵兴嗽逝澳腊蛹臃刘辖锈秘诬法落卒切割树treecut---题意简述切割