题意
给出一个森林，求任意两点之间的距离。若两者不在一棵树上，输出“Not connected”，否则输出两点之间最短距离。
解题
如果在一棵树上，显然最短距离为u–>lca(u,v)–>v路径上权值之和。设d[u]表示节点u到根节点的距离。
此题卡内存，不能用下面方式存lca。
q[i].lca=q[i^1].lca=find(v);使前向星只存to和next，不存from和lca。lca用下面方式存
lca[i>>1]=find(v);//第i条边和第i^1条边都对应第i>>1个查询。AC代码
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=1e4+7;
const int maxc=1e6+7;
struct edge
{int to,next,w;
}e[maxn<<1];
struct query
{int to,next;
}q[maxc<<1];
int lca[maxc];
int head[maxn],first[maxn],cnt,tot;
int par[maxn],n,d[maxn];
bool vis[maxn],V[maxn];
void init()
{for(int i=0;i<=n;i++) d[i]=0;for(int i=0;i<=n;i++) vis[i]=false;for(int i=0;i<=n;i++) V[i]=false;for(int i=0;i<=n;i++) par[i]=i;for(int i=0;i<=n;i++) head[i]=-1;cnt=-1;for(int i=0;i<=n;i++) first[i]=-1;tot=-1;
}
void add_edge(int u,int v,int w)
{e[++cnt].to=v;e[cnt].w=w;e[cnt].next=head[u];head[u]=cnt;
}
void add_query(int u,int v)
{q[++tot].to=v;q[tot].next=first[u];first[u]=tot;
}
int find(int x)
{return par[x]==x?x:par[x]=find(par[x]);
}
void unit(int x,int y)
{int fx=find(x),fy=find(y);if(fx==fy) return ;par[fy]=fx;
}
void tarjan(int u)
{vis[u]=true;V[u]=true;for(int i=head[u];i!=-1;i=e[i].next){int v=e[i].to;if(vis[v]) continue;d[v]=d[u]+e[i].w;tarjan(v);unit(u,v);}for(int i=first[u];i!=-1;i=q[i].next){int v=q[i].to;if(!vis[v]) continue;lca[i>>1]=d[u]+d[v]-(d[find(v)]<<1);}
}int main()
{int m,c;while(~scanf("%d%d%d",&n,&m,&c)){init();for(int i=1;i<=m;i++){int u,v,w;scanf("%d%d%d",&u,&v,&w);add_edge(u,v,w);add_edge(v,u,w);}for(int i=0;i<c;i++){int u,v;scanf("%d%d",&u,&v);add_query(u,v);add_query(v,u);}for(int i=0;i<maxc;i++) lca[i]=-1;for(int i=1;i<=n;i++){if(!V[i]){memset(vis,0,sizeof(vis));tarjan(i);}}for(int i=0;i<c;i++){if(lca[i]==-1)printf("Not connected\n");elseprintf("%d\n",lca[i]);}}return 0;
}