题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2874
题目大意：给出n个点，m条边，q个询问，每次询问(u,v)的最短距离，若(u,v)不连通即不在同一颗树上则输出“Not connected”。
解题思路：这题也是模板题，有所不同的是这次给出的是森林而不是一棵树，所以vis数组得稍作修改，标记vis数组的是当前树的编号。下面给出Tarjan和倍增法两种解法。
Tarjan（离线）写法，被MLE坑了，离线写法必须要用静态邻接表，因为虽然n不大，但是q很大，所以如果存储问题邻接表会超内存。
还有突然脑残把dis[x]+dis[y]-2*dis[lca(x,y)]写成dis[x]+dis[y]-dis[lca(x,y)]漏了个2看了半天！！！MDZZ！！！
代码
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int N=1e4+;
const int M=1e6+; struct qnode{
int to,id,next;
}q[M*]; struct node{
int to,w,next;
}edge[N*]; int n,m,cnt,num,idx1,idx2;
int res[M],root[N],vis[N],dis[N],head1[N],head2[N]; void addedge(int u,int v,int w){
edge[idx1].to=v;
edge[idx1].w=w;
edge[idx1].next=head1[u];
head1[u]=idx1++;
} void addq(int u,int v,int id){
q[idx2].to=v;
q[idx2].id=id;
q[idx2].next=head2[u];
head2[u]=idx2++;
} int find(int x){
return root[x]==x?x:root[x]=find(root[x]);
} void init(){
cnt=num=;
idx1=idx2=;
for(int i=;i<=n;i++) root[i]=i;
memset(res,-,sizeof(res));
memset(vis,,sizeof(vis));
memset(dis,,sizeof(dis));
memset(head1,,sizeof(head1));
memset(head2,,sizeof(head2));
} void lca(int u,int num){
//注意这里vis[u]标记的是树的编号,为了判断点是否在同一颗树上
vis[u]=num;
//root[u]=u;
for(int i=head1[u];i;i=edge[i].next){
node t=edge[i];
if(!vis[t.to]){
dis[t.to]=dis[u]+t.w;
lca(t.to,num);
root[t.to]=u;
}
}
for(int i=head2[u];i;i=q[i].next){
qnode t=q[i];
//属于同一颗树
if(vis[t.to]==num)
res[t.id]=dis[t.to]+dis[u]-*dis[find(t.to)];
}
} int main(){
int t;
while(~scanf("%d%d%d",&n,&m,&t)){
init();
for(int i=;i<=m;i++){
int a,b,w;
scanf("%d%d%d",&a,&b,&w);
addedge(a,b,w);
addedge(b,a,w);
}
for(int i=;i<=t;i++){
int a,b;
scanf("%d%d",&a,&b);
addq(a,b,i);
addq(b,a,i);
}
//森林
for(int i=;i<=n;i++){
if(!vis[i]) lca(i,i);
}
for(int i=;i<=t;i++){
if(res[i]==-)
puts("Not connected");
else
printf("%d\n",res[i]);
}
}
return ;
}
倍增法（在线）写法，这个倒是不卡vector了，解决了上面所有问题后，我又脑残了的，我TM忘记调用bz()函数了！！！干瞪着瞪了两个小时两个小时啊！！！
所以这道水题弄了我一个下午。。。。噗！
代码
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int N=1e5+; struct node{
int to,w;
node(int to,int w):to(to),w(w){}
}; int n,m,q;
int fa[N][],depth[N],vis[N],dis[N];
vector<node>v[N]; void init(){
for(int i=;i<=n;i++) v[i].clear();
memset(vis,,sizeof(vis));
memset(depth,,sizeof(depth));
memset(dis,,sizeof(dis));
memset(fa,,sizeof(fa));
} void dfs(int u,int num){
vis[u]=num;
for(int i=;i<v[u].size();i++){
node t=v[u][i];
if(!vis[t.to]){
depth[t.to]=depth[u]+;
fa[t.to][]=u;
dis[t.to]=dis[u]+t.w;
dfs(t.to,num);
}
}
} //倍增,处理fa数组
void bz(){
for(int j=;j<=;j++){
for(int i=;i<=n;i++){
fa[i][j]=fa[fa[i][j-]][j-];
}
}
} int lca(int x,int y){
//保证深度大的点为x
if(depth[x]<depth[y])
swap(x,y);
int dc=depth[x]-depth[y];
for(int i=;i<;i++){
if(<<i&dc) //一个判断，模拟下就会清楚
x=fa[x][i];
}
if(x==y) return x; //如果深度一样，两个点相同，直接返回
for(int i=;i>=;i--){
if(fa[x][i]!=fa[y][i]){ //跳2^i不一样，就跳，否则不跳
x=fa[x][i];
y=fa[y][i];
}
}
return fa[x][];
} int main(){
while(~scanf("%d%d%d",&n,&m,&q)){
init(); //初始化
for(int i=;i<=m;i++){
int a,b,w;
scanf("%d%d%d",&a,&b,&w);
v[a].push_back(node(b,w));
v[b].push_back(node(a,w));
}
for(int i=;i<=n;i++){
if(!vis[i]) dfs(i,i);
}
bz(); //一定别忘了啊！！！
for(int i=;i<=q;i++){
int x,y;
scanf("%d%d",&x,&y);
if(vis[x]!=vis[y])
puts("Not connected");
else
printf("%d\n",dis[x]+dis[y]-*dis[lca(x,y)]);
}
}
return ;
}