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

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

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

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

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

5、egin max:=d; maxi:=x; maxj:=y; end;end;if dumaxidumaxj then root:=maxi else root:=maxj; 找一個根，為邊權(quá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)計個數(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; 計算end;/=beginassign(input,hookey.in); reset(input);assign(output,hookey.out); rewrite(output); init;fil