题意：现在有 n 个点与 m 条边的无向无环图，但是图不一定完全连通，边有各自的边权，给出多组询问，查询两点之间的路径权值和，或者输出两点不连通。
一开始有最短路的想法，但是由于询问有 1e6 组，做单源最短路肯定会爆炸，而 1e4 的边数又觉得 floyd 时间空间都会炸，又因为是无环图，所以就想到了LCA的做法，大量询问让我很自然地就想到了离线Tarjan。由于不连通，就分多次Tarjan，通过标记来实现是否在同一棵树中。离线Tarjan 搞了一发结果就原来的做法估计是因为vector中的pair需要存问题编号或者是vector本身的原因，总之一直 MLE ，看了 discuss 有人提供了一种问题的存储方法，就是将所有问题也像链式前向星的方法存储，而节点编号分别是 0/1,2/3，这样的，只要用 节点编号/2 就能确定是哪个问题的结果。这样A掉了。但是不能忍的是我看见别人的题解里写的做法是直接递归向上爬LCA的做法……而且不是倍增！是一步一步爬的！递归！而且我交了一发还比离线快！这什么数据啊！卡空间不卡时间！暴力都能过！还更快！我不服！
1 #include2 #include 3 4 const int maxn=1e4+1; 5 const int maxm=2e4+1; 6 const int maxq=1e6+1; 7 8 int n; 9 int head[maxn],nxt[maxm],point[maxm],val[maxm],size;10 int fa[maxn],dis[maxn];11 int vis1[maxn];12 int ans[maxq];13 int head1[maxn],point1[maxq<<1],nxt1[maxq<<1],size1;14 int cnt;15 16 void init(){17 memset(head,-1,sizeof(head));18 size=0;19 memset(head1,-1,sizeof(head1));20 size1=0;21 memset(vis1,0,sizeof(vis1));22 for(int i=1;i<=n;++i)fa[i]=i;23 memset(ans,-1,sizeof(ans));24 cnt=0;25 }26 27 void add(int a,int b,int v){28 point[size]=b;29 val[size]=v;30 nxt[size]=head[a];31 head[a]=size++;32 point[size]=a;33 val[size]=v;34 nxt[size]=head[b];35 head[b]=size++;36 }37 38 int find(int x){39 return x==fa[x]?x:fa[x]=find(fa[x]);40 }41 42 void Tarjan(int s,int pre){43 for(int i=head[s];~i;i=nxt[i]){44 int j=point[i];45 if(j!=pre){46 dis[j]=dis[s]+val[i];47 Tarjan(j,s);48 int x=find(j),y=find(s);49 if(x!=y)fa[x]=y;50 }51 }52 vis1[s]=cnt;53 for(int i=head1[s];~i;i=nxt1[i]){54 int j=point1[i];55 if(vis1[j]==vis1[s]){56 int lca=find(j);57 int id=i/2;58 ans[id]=dis[s]+dis[j]-2*dis[lca];59 }60 }61 }62 63 int main(){64 int m,k;65 while(scanf("%d%d%d",&n,&m,&k)!=EOF){66 init();67 while(m--){68 int a,b,v;69 scanf("%d%d%d",&a,&b,&v);70 add(a,b,v);71 }72 for(int i=0;i