切割树 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---题意简述切割