逃学的小孩 两次遍历 树型DP

1、NOI 2003逃学的小孩两次遍历树型DPChris家的电话铃响起了，里面传出了 Chris的老师焦急的声音：“喂，是Chris的家长吗？你们的孩子又没来上课，不想参加考试了吗？” 一听说要考试，Chris的父母就心急如焚，他们决定在尽量短的时间内找到Chris。他们告诉Chris的老师：“根据以往的经验，Chris现在必然躲 在朋友Shermie或Yashiro家里偷玩拳皇游戏。现在，我们就从家出发去找Chris，一但找到，我们立刻给您打电话。”说完砰的一声把电 话挂了。Chris居住的城市由N个居住点和若干条连接居住点的双向街道组成，经过街道x需花费Tx分钟。可以保证，任两个居住点间有且仅

2、有一 条通路。Chris家在点C，Shermie和Yashiro分别住在点A和点B。Chris的老师和Chris的父母都有城市地图，但:hris的父母知道点A、B、C 的具体位置而。什1,的老师不知。为了尽快找到Chris，Chris的父母会遵守以下两条规则：如果A距离C比B距离C近，那么Chris的父母先去Shermie家寻找Chris，如果找不到，Chris的父母再去Yashiro家；反之亦然。Chris的父母总沿着两点间唯一的通路行走。显然，Chris的老师知道Chris的父母在寻找Chris的过程中会遵守以上两条规则，但由于他并不知道A，B，C的具体位置，所以现在他希 望你告诉他，最坏

3、情况下Chris的父母要耗费多长时间才能找到Chris？OO例如上图，这座城市由4个居住点和3条街道组成，经过每条街道均需花费1分钟时间。假设Chris住在点C，Shermie住在点A，Yashiro 住在点B，因为C到B的距离小于C到A的距离，所以Chiris的父母会先去Yashiro家寻找Chris，一旦找不到，再去Shermie家寻找。这样， 最坏情况下Chris的父母需要花费4分钟的时间才能找到Chris。Input输入的第一行是两个整数N（3 N 200000）和M，分别表示居住点总数和街道总数。以下M行，每行给出一条街道的信息。第i+1行 包含整数4、V、Ti（ 1Ur Vi N，

4、1 Ti 1000000000），表示街道i连接居住点Ui和*并且经过街道i需花费Ti分钟。街道信息不会重复 给出。Output输出仅包含整数T，即最坏情况下Chris的父母需要花费T分钟才能找到Chris。Sample Input4 3 TOC o 1-5 h z 2 13 14 1Sample Output4Hint数据规模有一定缩减，建议使用scanf读入数据 SourceNOI2003【题目】：逃学的小孩【类型】：动态规划 【难度】：3.5【来源】：NOI 2003【关键字】：两次遍历 树型DP 【题目大意】：在一颗树上，有ABC三个点，A为起点，ABmax then 记录边权最大值b

5、egin max:=d; maxi:=x; maxj:=y; end;end;if dumaxidumaxj then root:=maxi else root:=maxj; 找一个根，为边权最大的两个端点中度最小的end;/=procedure swap(var a,b:qword); 交换var t:qword;begin t:=a; a:=b; b:=t; end;/=procedure swap2(var a,b:longint); 交换var t:longint;begin t:=a; a:=b; b:=t; end;/=function dfs(x:longint):longint

6、; 第一次 DFS var y,t:longint; tmp:qword;beginvx:=true; max1x:=0; max2x:=0; from1x:=x; from2x:=x; t:=firstx;while t0 dobeginy:=gt.y;if not vy then begin tmp:=dfs(y)+gt.d; 统计个数 if tmpmax2x then begin swap(tmp,max2x); swap2(y,from2x); end; if max2xmax1x then begin swap(max2x,max1x); swap2(from2x,from1x);

7、end; 更新end;t:=gt.next;end;exit(max1x)end;/=procedure treedp(x:longint; max:qword); 第二次 DFS var y,t:longint; t1,t2,t3:qword;beginvx:=true; t:=firstx;while t0 dobeginy:=gt.y;if not vy thenbeginif from1xy then 若可以取最大值则取，否则取次大值begin if max1xmax then treedp(y,max1x+gt.d) else treedp(y,max+gt.d); end else

8、begin if max2xmax then treedp(y,max2x+gt.d) else treedp(y,max+gt.d); end;end;t:=gt.next;end;t1:=max1x; t2:=max2x; t3:=max;if t3t2 then swap(t3,t2);if t2t1 then swap(t2,t1);if t1+2*t2+t3ans then ans:=t1+2*t2+t3; 计算end;/=beginassign(input,hookey.in); reset(input);assign(output,hookey.out); rewrite(output); init;fil