逃學(xué)的小孩 兩次遍歷 樹(shù)型DP

1、NOI 2003逃學(xué)的小孩兩次遍歷樹(shù)型DPChris家的電話鈴響起了，里面?zhèn)鞒隽?Chris的老師焦急的聲音：“喂，是Chris的家長(zhǎng)嗎？你們的孩子又沒(méi)來(lái)上課，不想?yún)⒓涌荚嚵藛幔俊?一聽(tīng)說(shuō)要考試，Chris的父母就心急如焚，他們決定在盡量短的時(shí)間內(nèi)找到Chris。他們告訴Chris的老師：“根據(jù)以往的經(jīng)驗(yàn)，Chris現(xiàn)在必然躲 在朋友Shermie或Yashiro家里偷玩拳皇游戲。現(xiàn)在，我們就從家出發(fā)去找Chris，一但找到，我們立刻給您打電話?！闭f(shuō)完砰的一聲把電 話掛了。Chris居住的城市由N個(gè)居住點(diǎn)和若干條連接居住點(diǎn)的雙向街道組成，經(jīng)過(guò)街道x需花費(fèi)Tx分鐘?？梢员ＷC，任兩個(gè)居住點(diǎn)間有且僅

2、有一 條通路。Chris家在點(diǎn)C，Shermie和Yashiro分別住在點(diǎn)A和點(diǎn)B。Chris的老師和Chris的父母都有城市地圖，但:hris的父母知道點(diǎn)A、B、C 的具體位置而。什1,的老師不知。為了盡快找到Chris，Chris的父母會(huì)遵守以下兩條規(guī)則：如果A距離C比B距離C近，那么Chris的父母先去Shermie家尋找Chris，如果找不到，Chris的父母再去Yashiro家；反之亦然。Chris的父母總沿著兩點(diǎn)間唯一的通路行走。顯然，Chris的老師知道Chris的父母在尋找Chris的過(guò)程中會(huì)遵守以上兩條規(guī)則，但由于他并不知道A，B，C的具體位置，所以現(xiàn)在他希 望你告訴他，最壞

3、情況下Chris的父母要耗費(fèi)多長(zhǎng)時(shí)間才能找到Chris？OO例如上圖，這座城市由4個(gè)居住點(diǎn)和3條街道組成，經(jīng)過(guò)每條街道均需花費(fèi)1分鐘時(shí)間。假設(shè)Chris住在點(diǎn)C，Shermie住在點(diǎn)A，Yashiro 住在點(diǎn)B，因?yàn)镃到B的距離小于C到A的距離，所以Chiris的父母會(huì)先去Yashiro家尋找Chris，一旦找不到，再去Shermie家尋找。這樣， 最壞情況下Chris的父母需要花費(fèi)4分鐘的時(shí)間才能找到Chris。Input輸入的第一行是兩個(gè)整數(shù)N（3 N 200000）和M，分別表示居住點(diǎn)總數(shù)和街道總數(shù)。以下M行，每行給出一條街道的信息。第i+1行 包含整數(shù)4、V、Ti（ 1Ur Vi N，

4、1 Ti 1000000000），表示街道i連接居住點(diǎn)Ui和*并且經(jīng)過(guò)街道i需花費(fèi)Ti分鐘。街道信息不會(huì)重復(fù) 給出。Output輸出僅包含整數(shù)T，即最壞情況下Chris的父母需要花費(fèi)T分鐘才能找到Chris。Sample Input4 3 TOC o 1-5 h z 2 13 14 1Sample Output4Hint數(shù)據(jù)規(guī)模有一定縮減，建議使用scanf讀入數(shù)據(jù) SourceNOI2003【題目】：逃學(xué)的小孩【類型】：動(dòng)態(tài)規(guī)劃 【難度】：3.5【來(lái)源】：NOI 2003【關(guān)鍵字】：兩次遍歷 樹(shù)型DP 【題目大意】：在一顆樹(shù)上，有ABC三個(gè)點(diǎn)，A為起點(diǎn)，ABmax then 記錄邊權(quán)最大值b

5、egin max:=d; maxi:=x; maxj:=y; end;end;if dumaxidumaxj then root:=maxi else root:=maxj; 找一個(gè)根，為邊權(quán)最大的兩個(gè)端點(diǎn)中度最小的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; 統(tǒng)計(jì)個(gè)數(shù) 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; 計(jì)算end;/=beginassign(input,hookey.in); reset(input);assign(output,hookey.out); rewrite(output); init;fil