题意：现在有 n 个点与 m 条边的无向无环图，但是图不一定完全连通，边有各自的边权，给出多组询问，查询两点之间的路径权值和，或者输出两点不连通。
一开始有最短路的想法，但是由于询问有 1e6 组，做单源最短路肯定会爆炸，而 1e4 的边数又觉得 floyd 时间空间都会炸，又因为是无环图，所以就想到了LCA的做法，大量询问让我很自然地就想到了离线Tarjan。由于不连通，就分多次Tarjan，通过标记来实现是否在同一棵树中。离线Tarjan 搞了一发结果就原来的做法估计是因为vector中的pair需要存问题编号或者是vector本身的原因，总之一直 MLE ，看了 discuss 有人提供了一种问题的存储方法，就是将所有问题也像链式前向星的方法存储，而节点编号分别是 0/1,2/3，这样的，只要用 节点编号/2 就能确定是哪个问题的结果。这样A掉了。但是不能忍的是我看见别人的题解里写的做法是直接递归向上爬LCA的做法……而且不是倍增！是一步一步爬的！递归！而且我交了一发还比离线快！这什么数据啊！卡空间不卡时间！暴力都能过！还更快！我不服！
#include<stdio.h>
#include<string.h> const int maxn=1e4+;
const int maxm=2e4+;
const int maxq=1e6+; int n;
int head[maxn],nxt[maxm],point[maxm],val[maxm],size;
int fa[maxn],dis[maxn];
int vis1[maxn];
int ans[maxq];
int head1[maxn],point1[maxq<<],nxt1[maxq<<],size1;
int cnt; void init(){
memset(head,-,sizeof(head));
size=;
memset(head1,-,sizeof(head1));
size1=;
memset(vis1,,sizeof(vis1));
for(int i=;i<=n;++i)fa[i]=i;
memset(ans,-,sizeof(ans));
cnt=;
} void add(int a,int b,int v){
point[size]=b;
val[size]=v;
nxt[size]=head[a];
head[a]=size++;
point[size]=a;
val[size]=v;
nxt[size]=head[b];
head[b]=size++;
} int find(int x){
return x==fa[x]?x:fa[x]=find(fa[x]);
} void Tarjan(int s,int pre){
for(int i=head[s];~i;i=nxt[i]){
int j=point[i];
if(j!=pre){
dis[j]=dis[s]+val[i];
Tarjan(j,s);
int x=find(j),y=find(s);
if(x!=y)fa[x]=y;
}
}
vis1[s]=cnt;
for(int i=head1[s];~i;i=nxt1[i]){
int j=point1[i];
if(vis1[j]==vis1[s]){
int lca=find(j);
int id=i/;
ans[id]=dis[s]+dis[j]-*dis[lca];
}
}
} int main(){
int m,k;
while(scanf("%d%d%d",&n,&m,&k)!=EOF){
init();
while(m--){
int a,b,v;
scanf("%d%d%d",&a,&b,&v);
add(a,b,v);
}
for(int i=;i<k;++i){
int a,b;
scanf("%d%d",&a,&b);
point1[size1]=b;
nxt1[size1]=head1[a];
head1[a]=size1++;
point1[size1]=a;
nxt1[size1]=head1[b];
head1[b]=size1++;
}
for(int i=;i<=n;++i){
if(!vis1[i]){
++cnt;
dis[i]=;
Tarjan(i,);
}
}
for(int i=;i<k;++i){
if(ans[i]==-)printf("Not connected\n");
else printf("%d\n",ans[i]);
}
}
return ;
}