比赛 |
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.