Đề bài:
Giải thích ví dụ
Truy vấn 1: Tìm tổ tiên chung gần nhất của các đỉnh được đánh số từ 2 đến 5, ở đây có thể thấy 2 là tổ tiên chung gần nhất của các đỉnh 2,3,4,5.
Truy vấn 2: Tìm tổ tiên chung gần nhất của các đỉnh được đánh số từ 1 đến 3, ở đây có thể thấy 1 là tổ tiên chung gần nhất của các đỉnh 1,2,3.
Truy vấn 3: Tìm tổ tiên chung gần nhất của các đỉnh được đánh số từ 4 đến 5, ở đây có thể thấy 3 là tổ tiên chung gần nhất của các đỉnh 4,5.
Thuật toán:
-
Có thể nhận thấy rằng tổ tiên chung gần nhất ( LCA ) của 3 đỉnh a,b,c sẽ bằng với LCA(a,LCA(c,b)). Dựa trên tính chất nãy ta có thể sử dụng Interval Tree để tìm LCA của 1 đoạn liên tiếp bằng cách tổ chức cây IT sẽ lưu LCA của các phần tử trong đoạn quản lý.
Các phần cơ bản của cây IT:
IT[id] = phần tử đang được quản lý khi đoạn quản lý gồm 1 phần tử.
IT[id] = LCA(IT[id*2],IT[id*2+1] ).
P/s : Có rất nhiều cách để tìm LCA ví dụ như : Sparse Table, Heavy Light Decomposition, Interval Tree, …
Code:
const tfi=''; tfo=''; var fi,fo:Text; ke,nx:array[-70000..70000] of longint; num,thoat,hd:array[0..70000] of longint; f:array[0..70000,0..20] of longint; n,q,jmax,dem,dem1:longint; t:array[0..3000000] of longint; procedure nhap; var i,j,u,v:longint; begin read(fi,n,q); for i:=1 to n-1 do begin read(fi,u,v); ke[i]:=v; nx[i]:=hd[u]; hd[u]:=i; ke[-i]:=u; nx[-i]:=hd[v]; hd[v]:=-i; end; for j:=1 to 20 do if 1 shl j<=n then jmax:=j+1; end; procedure DFS(u:longint); var j,v:longint; begin inc(dem); num[u]:=dem; for j:=1 to jmax do f[u,j]:=f[f[u,j-1],j-1]; j:=hd[u]; while j<>0 do begin v:=ke[j]; if f[v,0]=0 then begin f[v,0]:=u; DFS(v); end; j:=nx[j]; end; inc(dem1); thoat[u]:=dem1; end; function cha(x,y:longint):boolean; begin cha:=(num[x]<=num[y]) and (thoat[y]<=thoat[x]); end; function lca(x,y:longint):longint; var j:longint; begin if cha(x,y) then exit(x); if cha(y,x) then exit(y); for j:=jmax downto 0 do if not cha(f[x,j],y) then x:=f[x,j]; exit(f[x,0]); end; procedure init(i,l,r:longint); var mid:longint; begin if l=r then begin t[i]:=l; exit; end; mid:=(l+r) div 2; init(i*2,l,mid); init(i*2+1,mid+1,r); t[i]:=lca(t[i*2],t[i*2+1]); end; function get(i,l,r,u,v:longint):longint; var mid:longint; begin if (l>v) or (r<u) then exit(u); if (u<=l) and (r<=v) then exit(t[i]); mid:=(l+r) div 2; get:=lca(get(i*2,l,mid,u,v),get(i*2+1,mid+1,r,u,v)); end; procedure xuli; var i,u,v,pa,j:longint; begin f[1,0]:=1; DFS(1); init(1,1,n); for i:=1 to q do begin read(fi,u,v); writeln(fo,get(1,1,n,u,v)); end; end; begin assign(fi,tfi); assign(fo,tfo); reset(fi); rewrite(fo); nhap; xuli; close(fo); end. |
Speak Your Mind