1602: [Usaco2008 Oct]牧场行走

  1 type
  2     point=^node;
  3     node=record
  4                g,w:longint;
  5                next:point;
  6     end;
  7 
  8 var
  9    i,j,k,l,m,n:longint;
 10    a,b:array[0..15,0..15000] of longint;
 11    c:array[0..15000] of point;
 12    d:array[0..15000] of longint;
 13 procedure swap(var x,y:longint);
 14           var z:longint;
 15           begin
 16                z:=x;x:=y;y:=z;
 17           end;
 18 procedure add(x,y,z:longint);
 19           var
 20              p:point;
 21           begin
 22                new(p);
 23                p^.w:=z;
 24                p^.g:=y;
 25                p^.next:=c[x];
 26                c[x]:=p;
 27           end;
 28 procedure dfs(x:longint);
 29           var
 30              p:point;
 31           begin
 32                p:=c[x];
 33                while p<>nil do
 34                      begin
 35                           if d[p^.g]=0 then
 36                              begin
 37                                   d[p^.g]:=d[x]+1;
 38                                   a[0,p^.g]:=x;
 39                                   b[0,p^.g]:=p^.w;
 40                                   dfs(p^.g);
 41                              end;
 42                           p:=p^.next;
 43                      end;
 44           end;
 45 function getfat(x,y:longint):longint;
 46          var i:longint;
 47          begin
 48               i:=0;
 49               while y>0 do
 50                     begin
 51                          if odd(y) then x:=a[i,x];
 52                          inc(i);
 53                          y:=y div 2;
 54                     end;
 55               exit(x);
 56          end;
 57 function getcom(x,y:longint):longint;
 58          var i,j:longint;
 59          begin
 60               if d[x]<d[y] then swap(x,y);
 61               x:=getfat(x,d[x]-d[y]);
 62               if x=y then exit(x);
 63               i:=15;
 64               while i>=0 do
 65                     begin
 66                          if a[i,x]<>a[i,y] then
 67                              begin
 68                                   x:=a[i,x];
 69                                   y:=a[i,y];
 70                              end;
 71                          dec(i);
 72                     end;
 73               exit(a[0,x]);
 74          end;
 75 function getsum(x,y:longint):longint;
 76          var i,j,k:longint;
 77          begin
 78               i:=0;j:=0;
 79               while y>0 do
 80                     begin
 81                          if odd(y) then
 82                             begin
 83                                  j:=j+b[i,x];
 84                                  x:=a[i,x];
 85                             end;
 86                          y:=y div 2;
 87                          inc(i);
 88                     end;
 89               exit(j);
 90          end;
 91 begin
 92      readln(n,m);
 93      for i:=1 to n do c[i]:=nil;
 94      for i:=1 to n-1 do
 95           begin
 96                readln(j,k,l);
 97                add(j,k,l);
 98                add(k,j,l);
 99           end;
100      fillchar(d,sizeof(d),0);
101      d[1]:=1;
102      dfs(1);
103 
104      for i:=1 to 15 do
105          for j:=1 to n do
106              a[i,j]:=a[i-1,a[i-1,j]];
107 
108      for i:=1 to 15 do
109          for j:=1 to n do
110              b[i,j]:=b[i-1,j]+b[i-1,a[i-1,j]];
111 
112      for i:=1 to m do
113          begin
114               readln(j,k);
115               l:=getcom(j,k);
116               writeln(getsum(j,d[j]-d[l])+getsum(k,d[k]-d[l]));
117          end;
118 end.