LCA
LCA 是最近公共祖先问题，一般是图变成树做的问题，如有n个点m-1条边等等这样的条件，LCA有在线离线算法，这里总结的是在线算法，而且用st算法加速。
算法分析
网上总结了一些博客：
http://blog.csdn.net/liangzhaoyang1/article/details/52549822
几题的变化都不大，可见模板的通用性。
Distance Queries
原题：poj 1986
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 4e4+5;
struct nod{
int to, cost;
nod(int a=0,int b=0){to = a; cost = b;}
};
int dep[maxn], se[maxn*2], no[maxn*2], fir[maxn], st[maxn*2][20], lo[200005];
vector<nod> g[maxn];
int n, m;
int cnt, sum;
void Init(){
for(int i = 0; i <= n; i++)
{
g[i].clear();
dep[i] = 0;
}
sum = cnt = 0;
}
void mkst(){
for(int i = 0; i <= cnt; i++) st[i][0] = se[i];
for(int j = 1; (1<<j) <= cnt; j++)
for(int i = 1; i <= cnt-(1<<j)+1; i++)
st[i][j] = min(st[i][j-1], st[i+(1<<(j-1))][j-1]);
}
void dfs(int u, int f, int di){
dep[u] = di;
no[++sum] = u;
int t = sum;
se[++cnt] = t;
fir[u] = cnt;//
/* for(auto p : g[u])
{
if(p.to == f) continue;
dfs(p.to, u, di+p.cost);
se[++cnt] = t;
}*/
for(int i = 0; i < g[u].size(); i++)
{
if(g[u][i].to == f) continue;
dfs(g[u][i].to, u, di+g[u][i].cost);
se[++cnt] = t;
}
}
int find(int p, int q){
if(p > q) swap(p, q);
int j = lo[q-p+1];
return min(st[p][j],st[q-(1<<j)+1][j]);
}
int cal(int x, int y){
int now = no[find(fir[x], fir[y])];
return dep[x] + dep[y] -2*dep[now];
}
int main(){
lo[1] = 0;
for(int i = 2; i <= 200000; i++) lo[i] = lo[i>>1]+1;
while(scanf("%d%d", &n, &m) != EOF){
Init();
for(int i = 1; i <= m; i++)
{
int x, y, dis;
char str[10];
scanf("%d%d%d%s", &x, &y, &dis, str);
g[x].push_back({y, dis});
g[y].push_back({x, dis});
}
dfs(1,0,0);mkst();
int q;
scanf("%d",&q);
while(q--)
{
int x, y;
scanf("%d%d", &x, &y);
printf("%d\n", cal(x, y));
}
}
return 0;
}
How far away？
原题：hdu 2586
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
#define pb push_back
const int maxn=40005;
int T;
int fir[maxn],no[2*maxn],se[2*maxn],st[2*maxn][20],lo[200005],dep[maxn];
bool used[maxn];
struct nod
{
int to,cost;
};
int n,m;
vector<nod> g[maxn];
int cnt,sum;
void mkST()
{
for(int i=1;i<=cnt;i++)st[i][0]=se[i];
for(int j=1;(1<<j)<=cnt;j++)
for(int i=1;i<=cnt-(1<<j)+1;i++)
st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]);
}
void DFS(int u,int f,int di)
{
dep[u]=di;
no[++sum]=u;
int t=sum;
se[++cnt]=t;
fir[u]=cnt;
for(auto p : g[u])
{
if(p.to==f)continue;
DFS(p.to,u,di+p.cost);
se[++cnt]=t;
}
}
int find(int p,int q)
{
if(p>q)swap(p,q);
int j=lo[q-p+1];
return min(st[p][j],st[q-(1<<j)+1][j]);
}
int cal(int x,int y)
{
int now=no[find(fir[x],fir[y])];
return dep[x]+dep[y]-2*dep[now];
}
int main()
{
lo[1]=0;
for(int i=2;i<=200000;i++)lo[i]=lo[i>>1]+1;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
for(int i=0;i<=n;i++)g[i].clear(),dep[i]=0;
cnt=sum=0;
for(int i=1;i<=n-1;i++)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
g[x].pb({y,z});g[y].pb({x,z});
}
DFS(1,0,0);mkST();
while(m--)
{
int x,y;
scanf("%d%d",&x,&y);
int d1=cal(x,y);
printf("%d\n",d1);
}
}
return 0;
}
Castle
原题：sidu 1247
#include<bits/stdc++.h>
using namespace std;
const double eps=1e-10;
const double pi=3.1415926535897932384626433832795;
const double eln=2.718281828459045235360287471352;
#define LL long long
#define IN freopen("in.txt", "r", stdin)
#define OUT freopen("out.txt", "w", stdout)
#define scan(x) scanf("%d", &x)
#define mp make_pair
#define pb push_back
#define sqr(x) (x) * (x)
#define pr(x) printf("Case %d: ",x)
#define prn(x) printf("Case %d:\n",x)
#define prr(x) printf("Case #%d: ",x)
#define prrn(x) printf("Case #%d:\n",x)
#define lowbit(x) (x&(-x))
const int maxn=30005;
int T;
int ftr[maxn],fir[maxn],no[2*maxn],se[2*maxn],st[2*maxn][20],lo[200005],dep[maxn];
bool used[maxn];
struct nod
{
int to,cost;
bool operator < (const struct nod p)const
{return cost>p.cost;}
};
priority_queue<nod> q;
int n,m;
vector<nod> g[maxn];
int cnt,sum;
int s1,s2,len;
int findftr(int t)
{
if(t==ftr[t])return t;
else return ftr[t]=findftr(ftr[t]);
}
void mkST()
{
for(int i=1;i<=cnt;i++)st[i][0]=se[i];
for(int j=1;(1<<j)<=cnt;j++)
for(int i=1;i<=cnt-(1<<j)+1;i++)
st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]);
}
void DFS(int u,int f,int di)
{
dep[u]=di;
no[++sum]=u;
int t=sum;
se[++cnt]=t;
fir[u]=cnt;
for(auto p : g[u])
{
if(p.to==f)continue;
DFS(p.to,u,di+p.cost);
se[++cnt]=t;
}
}
int find(int p,int q)
{
if(p>q)swap(p,q);
int j=lo[q-p+1];
return min(st[p][j],st[q-(1<<j)+1][j]);
}
int cal(int x,int y)
{
int now=no[find(fir[x],fir[y])];
return dep[x]+dep[y]-2*dep[now];
}
int main()
{
lo[1]=0;
for(int i=2;i<=200000;i++)lo[i]=lo[i>>1]+1;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
for(int i=0;i<=n;i++)g[i].clear(),dep[i]=0,ftr[i]=i;
cnt=sum=0;
for(int i=1;i<=n;i++)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
x++;y++;
int xx=findftr(x),yy=findftr(y);
if(xx==yy)
{
s1=x;s2=y;len=z;
continue;
}
g[x].pb({y,z});g[y].pb({x,z});
ftr[xx]=ftr[yy];
}
DFS(1,0,0);mkST();
while(m--)
{
int x,y;
scanf("%d%d",&x,&y);
x++;y++;
int d1=cal(x,y);
int d2=cal(x,s1)+cal(y,s2)+len;
int d3=cal(x,s2)+cal(y,s1)+len;
printf("%d\n",min(d1,min(d2,d3)));
}
}
return 0;
}