PWALK - Dạo chơi đồng cỏ
Tác giả: ll931110
Ngôn ngữ: Pascal
Program PWALK;
Const
input = '';
output = '';
Var
n,q: integer;
head,adj,adjcost,trace,x,y,c: array[1..2000] of integer;
fi,fo: text;
Procedure LoadGraph;
Var
i: integer;
Begin
Assign(fi, input);
Reset(fi);
Fillchar(head, sizeof(head), 0);
Readln(fi, n, q);
For i:= 1 to n - 1 do
Begin
Readln(fi, x[i], y[i], c[i]);
inc(head[x[i]]);
inc(head[y[i]]);
End;
For i:= 2 to n do head[i]:= head[i] + head[i - 1];
For i:= 1 to n - 1 do
Begin
adj[head[x[i]]]:= y[i];
adjcost[head[x[i]]]:= c[i];
dec(head[x[i]]);
adj[head[y[i]]]:= x[i];
adjcost[head[y[i]]]:= c[i];
dec(head[y[i]]);
End;
head[n + 1]:= 2 * (n - 1);
End;
Procedure DFS(u: integer);
Var
v: integer;
Begin
For v:= head[u] + 1 to head[u + 1] do
if trace[adj[v]] = 0 then
Begin
Trace[adj[v]]:= u;
DFS(adj[v]);
End;
End;
Procedure solve;
Var
i,v,s,f: integer;
sum: longint;
Begin
Assign(fo, output);
Rewrite(fo);
For i:= 1 to q do
Begin
Fillchar(trace, sizeof(trace), 0);
sum:= 0;
Readln(fi, s, f);
DFS(s);
While f <> s do
Begin
For v:= head[f] + 1 to head[f + 1] do
If adj[v] = trace[f] then
Begin
sum:= sum + adjcost[v];
Break;
End;
f:= trace[f];
End;
Writeln(fo, sum);
End;
Close(fo);
Close(fi);
End;
Begin
LoadGraph;
solve;
End.