Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

Tarjan离线，详细AC代码（有注释），1A刷进头版

Posted by xszxxc at 2015-09-24 09:43:41 on Problem 3728
```type
edge=record
fr,re,next:longint;
end;
var
i,n,tq,x,y,root,aux,tot,cnt:longint;
e,q,t:array[0..200000] of edge;
fa,down,up,mn,mx,f,g,h,ans,v:array[0..100010] of longint;
vs:array[0..100010] of boolean;
function min(x,y:longint):longint;begin if x<y then exit(x);exit(y);end;
function max(x,y:longint):longint;begin if x>y then exit(x);exit(y);end;
procedure add(x,y:longint);begin inc(cnt);with e[cnt] do begin re:=y;next:=f[x];end;f[x]:=cnt;end;         //树边集
procedure adde(x,y:longint);begin inc(tot);with q[tot] do begin fr:=x;re:=y;next:=g[x];end;g[x]:=tot;end;  //询问边集
procedure addans(x,y:longint);begin inc(aux);with t[aux] do begin re:=y;next:=h[x];end;h[x]:=aux;end;      //以该点为LCA的边集
//带权并查集操作
function find(x:longint):longint;
begin
if fa[x]=x then exit(x);
find:=find(fa[x]);
up[x]:=max(max(up[x],up[fa[x]]),mx[fa[x]]-mn[x]);
down[x]:=max(max(down[x],down[fa[x]]),mx[x]-mn[fa[x]]);
mx[x]:=max(mx[x],mx[fa[x]]);
mn[x]:=min(mn[x],mn[fa[x]]);
fa[x]:=find;
end;

procedure tarjan(x:longint);
var tmp,k:longint;
begin
//遍历与该点相关的全部询问，若另一点已被访问过，则可确定两点的LCA即为另一点所属集合的祖先，并将计算结果的任务交给LCA
tmp:=g[x];
while tmp<>0 do
begin
with q[tmp] do
tmp:=q[tmp].next;
end;
//根据DFS序标记该点已被访问
vs[x]:=true;
//遍历该点的子节点
tmp:=f[x];
while tmp<>0 do
begin
with e[tmp] do
if not vs[re] then
begin
tarjan(re);
fa[re]:=x;
end;
tmp:=e[tmp].next;
end;
//遍历以该点为LCA的全部询问，计算答案
tmp:=h[x];
while tmp<>0 do
begin
k:=t[tmp].re;
if odd(k) then k:=k xor 1;
with q[k] do
begin
find(fr);find(re);
ans[k>>1]:=max(max(up[fr],down[re]),mx[re]-mn[fr]);
end;
tmp:=t[tmp].next;
end;
end;

begin
randomize;
tot:=1;cnt:=1;aux:=1;
for i:=1 to n do read(v[i]);
//预处理并查集
for i:=1 to n do
begin
fa[i]:=i;mx[i]:=v[i];mn[i]:=v[i];
end;
for i:=1 to n-1 do
begin
end;
//询问添边
for i:=1 to tq do
begin
end;
root:=random(n)+1;
tarjan(root);
for i:=1 to tq do
writeln(ans[i]);
end.```

Followed by: