拉力赛 (Standard IO)

题意/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)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。