倍增这种东西，听起来挺高级，其实功能还没有线段树强大。线段树支持修改、查询，而倍增却不能支持修改，但是代码比线段树简单得多，而且当倍增这种思想被应用到树上时，它的价值就跟坐火箭一样，噌噌噌地往上涨。
关于倍增思想：
倍增的思想很简单：通过区间[1,2i-1]与[1+2i-1,2i(2i-1+2i-1)]求出区间[1,2i]。
所以它可以用于区间求最值，求和。而到了树上之后，就变成了，求它往上任意次的祖先。
而倍增求LCA，就是用到了倍增这个功能。
倍增求LCA算法思路：
f[i,j]，表示结点i，向上跳2j次跳到的点为f[i,j]。
显然f[i,0]中存的是i结点的父亲。
而f[i,j]=f[f[i,j-1],j-1]，所以我们可以很简单的就求出f数组。
那么我们应该如何用它来求LCA呢？
两个结点a，b。（假设a的深度小于b）
首先我们让两个结点跳到同一深度（那个深度小跳到哪儿），这个过程可以用倍增来加速：从大到小枚举i，判断b往上跳2i是否会超过a，如果会，就不跳，不会，就跳。
这个为什么对于每个2i最多只会跳一次呢？
——你跳两次2i，我不会直接跳一次2i+1吗，动动脚趾都知道了嘛！
当它们处于同一高度时会产生两种情况：1、a=b，说明a本来就是b的祖先。2、a<>b，这个时候我们也是从大到小枚举i，判断a和b两者都向上跳2i次（假设此时在结点C，D）会不会重合，若重合，说明它们的LCA在C的下面，不跳，若不重合则说明LCA在C、D的上面，那么就让a跳到C，b跳到D。最后再把a（或b）往上跳1次，就是LCA了！
那么为什么最后要向上跳一次呢？
——如果在某时刻我们往上跳2i次就能跳到LCA的话，那么C就会与D重合，所以并不会跳上去，而是会往上跳（2i-1+2i-2+...+21+20）次。所以我们在最后取其父亲就能够得到LCA了。
代码：
var f:array[0..100000,0..20]of longint; next,dist,vet:array[0..200000]of longint; x,y,z,a,b,i,j,k,n,m,tot,ans,sum:longint;procedure add(x,y,z:longint);begin inc(tot); next[tot]:=head[x]; vet[tot]:=y; head[x]:=tot; dist[tot]:=z;end;procedure dfs(u,dep:longint);var i,v:longint;begin depth[u]:=dep; vis[u]:=true; for i:=1 to 20 do f[u,i]:=f[f[u,i-1],i-1]; i:=head[u]; while i<>0 do begin v:=vet[i]; if not vis[v] then begin f[v,0]:=u; dfs(v,dep+1); end; i:=next[i]; end;end;function lca(a,b:longint):longint;var i,t:longint;begin if depth[a]>depth[b] then begin t:=a; a:=b; b:=t; end; for i:=20 downto 0 do if depth[f[b,i]]>=depth[a] then b:=f[b,i]; if a=b then exit(a); for i:=20 downto 0 do if f[a,i]<>f[b,i] then begin a:=f[a,i]; b:=f[b,i]; end; exit(f[a,0]);end;begin read(n); for i:=1 to n-1 do begin read(x,y,z); add(x,y,z); add(y,x,z); end; dfs(1,1); read(m); for i:=1 to m do begin read(x,y); writeln(lca(x,y)); end;end.