题意：给你一个含n条边的带权无向连通图，q次查询，每次查询两点间的最短距离。
思路：LCA+思维。
设a，b两点间的距离为f(a,b) 则f(a,b)=dis[a]+dis[b]-2*dis[lca(a,b)];
由于n条边，因此我们先任取一条边，设这条边为X，Y，权值为Z，设查询的点为x，y，则答案为
min(f(a,b),f(a,X)+f(b,X),f(a,Y)+f(b,Y),f(a,X)+f(b,Y)+Z,f(a,Y)+f(b,X)+Z);
#include<bits/stdc++.h>
#define lson (i<<1)
#define rson (i<<1|1) using namespace std;
typedef long long ll;
const int N =1e5+; struct node
{
int u,v,next;
int id,f;
ll w;
}edge[N*]; struct node1
{
int l,r;
ll w;
ll lz;
}tr[N<<]; int tot,head[N];
int n,q;
int anc[N<<][]; int dfn;
int dfns[N*];
int dep[N*];
int pos[N];
int inde[N];
int L[N];
int R[N];
int clo; int to[N];
int vis[N];
ll ww[N]; int uu,vv;
ll cost;
int huan;
int idd; void init()
{
tot=;
memset(head,-,sizeof(head));
memset(vis,,sizeof(vis));
memset(inde,-,sizeof(inde));
memset(pos,-,sizeof(pos));
clo=; huan=; idd=; dfn=; /// dfn竟然没清零 MMP
} void add(int u,int v,ll w,int id)
{
edge[++tot].u=u; edge[tot].v=v; edge[tot].id=id; edge[tot].w=w; edge[tot].f=;
edge[tot].next=head[u]; head[u]=tot;
} void dfs1(int u,int fa)
{
if(vis[u]){
uu=fa; vv=u; huan=; return ;
}
vis[u]=;
for(int i=head[u];i!=-;i=edge[i].next)
{
int v=edge[i].v;
if(v==fa) continue;
dfs1(v,u);
}
} void dfs2(int u,int deep) /// dfs序
{
//cout<<" u "<<u<<" deep "<<deep<<endl;
dfns[dfn]=u; dep[dfn]=deep; pos[u]=dfn++;
L[u]=++clo;
inde[u]=L[u]; /// 记录u在线段树中的位置
for(int i=head[u];i!=-;i=edge[i].next){
if(edge[i].f) continue; /// 如果是标记的边跳过
int v=edge[i].v;
if(pos[v]==-){
to[edge[i].id]=v; /// 表示这条边指向哪个点？
dfs2(v,deep+);
dfns[dfn]=u; dep[dfn++]=deep;
}
}
R[u]=clo;
} void init_RMQ(int n) /// dfn
{
for(int i=;i<=n;++i) anc[i][]=i;
for(int j=;(<<j)<=n;++j)
for(int i=;i+(<<j)-<=n;++i){
if(dep[anc[i][j-]]<dep[anc[i+(<<(j-))][j-]]) anc[i][j]=anc[i][j-];
else anc[i][j]=anc[i+(<<(j-))][j-];
}
} inline int RMQ(int L,int R)
{
int k=;
while(<<(k+)<=R-L+) ++k;
if(dep[anc[L][k]]<dep[anc[R-(<<k)+][k]]) return anc[L][k];
return anc[R-(<<k)+][k];
} inline int LCA(int u,int v)
{
if(pos[u]>pos[v]) return dfns[RMQ(pos[v],pos[u])];
return dfns[RMQ(pos[u],pos[v])];
} void push_up(int i)
{
tr[i].w=tr[lson].w+tr[rson].w;
} void push_down(int i)
{
if(tr[i].lz){ /// 查询只有点查询，所以不必更新区间点的sum
ll &lz=tr[i].lz;
tr[lson].lz+=lz; tr[rson].lz+=lz;
tr[lson].w+=lz; tr[rson].w+=lz;
lz=;
}
} void build(int i,int l,int r)
{
tr[i].l=l; tr[i].r=r; tr[i].w=; tr[i].lz=;
if(l==r) return ;
int mid=(l+r)>>;
build(lson,l,mid);
build(rson,mid+,r);
} void update(int i,int l,int r,ll w)
{
if(tr[i].l==l&&tr[i].r==r){
tr[i].lz+=w; tr[i].w+=w;
return ;
}
push_down(i);
int mid=(tr[i].l+tr[i].r)>>;
if(r<=mid) update(lson,l,r,w);
else if(l>mid ) update(rson,l,r,w);
else{
update(lson,l,mid,w);
update(rson,mid+,r,w);
}
push_up(i);
} ll query(int i,int aim)
{
if(tr[i].l==tr[i].r&&tr[i].l==aim){
return tr[i].w;
}
push_down(i);
int mid=(tr[i].l+tr[i].r)>>;
if(aim<=mid) return query(lson,aim);
else return query(rson,aim);
} ll getans(int u,int v)
{
int lca=LCA(u,v);
ll sum1,sum2,sum3;
sum1=query(,L[u]); sum2=query(,L[v]);
sum3=query(,L[lca]);
return sum1+sum2-sum3*;
} int main()
{
int T;
int u,v,op;
ll w;
scanf("%d",&T);
while(T--)
{
scanf("%d %d",&n,&q);
init();
for(int i=;i<=n;i++){
scanf("%d %d %lld",&u,&v,&w);
add(u,v,w,i);
add(v,u,w,i);
ww[i]=w;
} dfs1(,-);/// 第一遍dfs 先找到环中的任意一条边
for(int i=;i<=tot;i++){ /// 给边打上标记
if((edge[i].u==uu&&edge[i].v==vv)||(edge[i].u==vv&&edge[i].v==uu)){
edge[i].f=;
idd=edge[i].id;
cost=edge[i].w;
}
}
dfs2(,);
/*cout<<"dfn "<<dfn<<endl;
cout<<uu<<" *** "<<vv<<endl;
for(int i=1;i<=n;i++){
cout<<"l "<<L[i]<<" r "<<R[i]<<endl;
}
*/
init_RMQ(dfn); build(,,n); /// 以dfs的遍历出的 L,R 建树 那么接下来就是一个区间更新，单点查询的问题了
for(int i=;i<=n;i++){
if(i==idd) continue;
u=to[i];
update(,L[u],R[u],ww[i]);
}
/*
for(int i=1;i<=n;i++){
ll tmp=query(1,L[i]);
cout<<" dis "<<tmp<<endl;
}
*/ while(q--)
{ scanf("%d %d",&u,&v);
ll ans=getans(u,v);
ans=min(ans,getans(uu,u)+getans(vv,v)+cost); /// 经过标记的路的两个不同的方向。
ans=min(ans,getans(uu,v)+getans(vv,u)+cost);
printf("%lld\n",ans); } }
return ;
}