題意/Description:

? ? ? ?車展結束后，游樂園決定舉辦一次盛大的山道拉力賽，平平和韻韻自然也要來參加大賽。
賽場上共有n個連通的計時點，n-1條賽道（構成了一棵樹）。每個計時點的高度都不相同（父結點的高度必然大于子結點），相鄰計時點間由賽道相連。由于馬力不夠，所以韻韻的遙控車只能從高處駛向低處。而且韻韻的車跑完每條賽道都需花費一定的時間。
? ? ? ?舉辦方共擬舉辦m個賽段的比賽，每次從第u個計時點到第v個計時點，當然其中有不少比賽韻韻的遙控車是不能參加的（因為要上坡）。平平想知道他能參加多少個賽段的比賽，并且想知道他完成這些賽段的總用時。

?

讀入/Input：

? ? ? ?第一行兩個整數n，m。
? ? ? ?接下來n-1行每行3個整數a、b、t。
? ? ? ?表示韻韻的遙控車可以花t秒從第a個計時點到第b個計時點。
? ? ? ?接下來m行每行2個整數u、v，意義如描述所示。

?

輸出/Output：

? ? ? ?第一行輸出一個正整數，表示能參加的賽段數。
? ? ? ?第二行輸出一個正整數，表示總用時。

?

題解/solution：

? ? ? ?求兩個點的LCA，但是有一個現實條件就是，兩個點之間一定要有一個點是另一個點的祖先，不然韻韻就無法參加（根據題意），所以判斷一下就行。注意要用int64！！！

?

代碼/Code：

?

typearr=recordy,w,next:longint;end; varn,m,nm:longint;ans,anss:int64;tu:array [0..20001] of arr;use:array [0..10001] of boolean;go:array [0..10001,0..20] of longint;ls,deep,sum:array [0..10001] of longint;procedure add(o,p,ww:longint); begininc(nm);with tu[nm] dobeginy:=p; w:=ww;next:=ls[o];ls[o]:=nm;end; end;procedure dfs(x,last:longint); vari:longint; begini:=ls[x];while i>0 dowith tu[i] dobeginif y<>last thenbegingo[y][0]:=x;deep[y]:=deep[x]+1;sum[y]:=sum[x]+w;dfs(y,x);end;i:=next;end; end;procedure try1(var x:longint; k:longint); vari:longint; beginfor i:=15 downto 0 doif ((1 shl i)) and k>0 then x:=go[x,i]; end;function LCA(x,y:longint):longint; vari:longint; beginif deep[x]>deep[y] then try1(x,deep[x]-deep[y]);if deep[y]>deep[x] then try1(y,deep[y]-deep[x]);if x=y then exit(x);for i:=15 downto 0 doif go[x,i]<>go[y,i] thenbeginx:=go[x,i];y:=go[y,i];end;exit(go[x,0]); end;procedure init; vari,x,y,w:longint; beginreadln(n,m);for i:=1 to n-1 dobeginreadln(x,y,w);add(x,y,w); add(y,x,w);use[y]:=true;end; end;procedure main; vart,i,j,x,y:longint; beginfor i:=1 to n doif not use[i] then t:=i;ans:=0; anss:=0;dfs(t,0);for i:=1 to 15 dofor j:=1 to n dogo[j,i]:=go[go[j,i-1],i-1];for i:=1 to m dobeginreadln(x,y);if lca(x,y)=x thenbegininc(ans);anss:=anss+(sum[y]-sum[x]);end;end;writeln(ans);write(anss); end;begininit;main; end.

?

轉載于:https://www.cnblogs.com/zyx-crying/p/9319665.html

總結

以上是生活随笔為你收集整理的拉力赛 (Standard IO)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。