拉力赛 (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：

type
  arr=record
    y,w,next:longint;
  end;
var
  n,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);
begin
  inc(nm);
  with tu[nm] do
    begin
      y:=p; w:=ww;
      next:=ls[o];
      ls[o]:=nm;
    end;
end;

procedure dfs(x,last:longint);
var
  i:longint;
begin
  i:=ls[x];
  while i>0 do
    with tu[i] do
      begin
        if y<>last then
          begin
            go[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);
var
  i:longint;
begin
  for i:=15 downto 0 do
    if ((1 shl i)) and k>0 then x:=go[x,i];
end;

function LCA(x,y:longint):longint;
var
  i:longint;
begin
  if 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 do
    if go[x,i]<>go[y,i] then
      begin
        x:=go[x,i];
        y:=go[y,i];
      end;
  exit(go[x,0]);
end;

procedure init;
var
  i,x,y,w:longint;
begin
  readln(n,m);
  for i:=1 to n-1 do
    begin
      readln(x,y,w);
      add(x,y,w); add(y,x,w);
      use[y]:=true;
    end;
end;

procedure main;
var
  t,i,j,x,y:longint;
begin
  for i:=1 to n do
    if not use[i] then t:=i;
  ans:=0; anss:=0;
  dfs(t,0);
  for i:=1 to 15 do
    for j:=1 to n do
      go[j,i]:=go[go[j,i-1],i-1];
  for i:=1 to m do
    begin
      readln(x,y);
      if lca(x,y)=x then
        begin
          inc(ans);
          anss:=anss+(sum[y]-sum[x]);
        end;
    end;
  writeln(ans);
  write(anss);
end;

begin
  init;
  main;
end.