比赛 ZLXOI2015Day2 评测结果 AAAAAAAATT
题目名称 ZLX的陨落 最终得分 80
用户昵称 ywx 运行时间 2.202 s
代码语言 Pascal 内存使用 7.41 MiB
提交时间 2015-10-30 21:07:20
显示代码纯文本
type point=record
     fa,qu,deep:longint;
     end;
var i,j,n,m,x2,y2,z2,dis,q:longint;
    x,y,z,x1,y1,z1,way,num:array[0..200000] of longint;
    tr:array[1..100000] of point;

procedure init;
begin
    readln(n,m);
  for i:=1 to m do
  begin
    readln(x2,y2,z2);
    x1[i]:=x2;
    y1[i]:=y2;
    z1[i]:=z2;
    inc(way[x2]);
    inc(way[y2]);
  end;

  for i:=2 to n do
  way[i]:=way[i-1]+way[i];

  for i:=1 to m do
  begin
    inc(num[x1[i]]);inc(num[y1[i]]);

    x[way[x1[i]-1]+num[x1[i]]]:=x1[i];
    y[way[x1[i]-1]+num[x1[i]]]:=y1[i];
    z[way[x1[i]-1]+num[x1[i]]]:=z1[i];
    x[way[y1[i]-1]+num[y1[i]]]:=y1[i];
    y[way[y1[i]-1]+num[y1[i]]]:=x1[i];
    z[way[y1[i]-1]+num[y1[i]]]:=z1[i];
 end;
end;

procedure LCA(x,y,dis:longint);
var i,j:longint;
begin
  if x=y then begin writeln(dis);exit;end;
  if tr[x].deep>tr[y].deep then LCA(tr[x].fa,y,dis+tr[x].qu);
  if tr[x].deep<tr[y].deep then LCA(x,tr[y].fa,dis+tr[y].qu);
  if tr[x].deep=tr[y].deep then LCA(tr[x].fa,tr[y].fa,dis+tr[x].qu+tr[y].qu);
end;

procedure maketree(now,fu,qq,dep:longint);
var i,j:longint;
begin
  tr[now].fa:=fu;
  tr[now].qu:=qq;
  tr[now].deep:=dep;

  for i:=way[now-1]+1 to way[now] do
  if y[i]<>tr[now].fa then maketree(y[i],now,z[i],dep+1);
end;

begin
  assign(input,'ThefallingofZLX.in');
  assign(output,'ThefallingofZLX.out');
  reset(input);
  rewrite(output);
  init;
  maketree(1,1,0,1);
  readln(q);
  for i:=1 to q do
  begin
    readln(x2,y2);
    dis:=0;
    LCA(x2,y2,dis);
  end;
  close(input);
  close(output);
end.