LCA倍增算法常见误区及优化模板分析

typenode&＃61;^link;link&＃61;recordnum:int64;next:node;end;varfa:array[0..300000,0..100] of int64;dep:array[0..300000] of int64;nd:array[0..300000] of node;b:array[0..300000] of boolean;dl:array[0..300000] of int64;n,m,maxdep,ans,t1,t2:int64;i:longint;procedure maketree;vart1,t2,head,tail:int64;i,j:longint;p:node;beginfor i:&＃61;0 to n dob[i]:&＃61;false;for i:&＃61;1 to n-1 dobeginread(t1,t2);new(p);p^.num:&＃61;t2;p^.next:&＃61;nd[t1];nd[t1]:&＃61;p;new(p);p^.num:&＃61;t1;p^.next:&＃61;nd[t2];nd[t2]:&＃61;p;end;new(p);head:&＃61;1;tail:&＃61;1;dl[head]:&＃61;1;b[1]:&＃61;true;while head<&＃61;tail dobeginp:&＃61;nd[dl[head]];while p<>nil dobeginif b[p^.num]&＃61;false thenbegininc(tail);dl[tail]:&＃61;p^.num;fa[p^.num,0]:&＃61;dl[head];dep[p^.num]:&＃61;dep[dl[head]]&＃43;1;b[p^.num]:&＃61;true;if dep[p^.num]>maxdep then maxdep:&＃61;dep[p^.num];end;p:&＃61;p^.next;end;inc(head);end;for j:&＃61;1 to trunc(ln(maxdep)/ln(2))&＃43;1 dofor i:&＃61;0 to n doif dep[i]>&＃61;1<thenfa[i,j]:&＃61;fa[fa[i,j-1],j-1];end;procedure lca(a,b:longint);vari,t:longint;beginif dep[a]>dep[b] thenbegint:&＃61;a;a:&＃61;b;b:&＃61;t;end;if dep[a]<>dep[b] thenfor i:&＃61;trunc(ln(dep[b]-dep[a])/ln(2))&＃43;10 downto 0 doif dep[b]-1<&＃61;dep[a] thenbeginb:&＃61;fa[b,i];ans:&＃61;ans&＃43;1<<i;end;if a<>b thenfor i:&＃61;trunc(ln(dep[a])/ln(2))&＃43;10 downto 0 doif fa[a,i]<>fa[b,i] thenbegina:&＃61;fa[a,i];b:&＃61;fa[b,i];ans:&＃61;ans&＃43;1<<(i&＃43;1);end;if a<>b then inc(ans,2);end;beginreadln(n);if n&＃61;1 thenbeginwriteln(0);halt; end;maketree;readln(m);read(t1);for i:&＃61;2 to m dobeginread(t2);lca(t1,t2);t1:&＃61;t2;end;writeln(ans);end.