最近公共祖先

dis[a,b]  =  dis[1,a]+dis[1,b]-2*dis[1,lca[a,b]];

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             using namespace std;#define inf 1000000000#define MAXN 40010struct edge{ int fr,to,w,next;}edg[MAXN*2],edg1[MAXN];int cnt,tot;int head[MAXN],head1[MAXN];bool vis[MAXN];void add(int u,int v,int w){ edg[cnt].fr=u; edg[cnt].to=v; edg[cnt].w=w; edg[cnt].next=head[u]; head[u]=cnt++;}void add1(int u,int v,int w){ edg1[tot].next=head1[u]; edg1[tot].to=v; edg1[tot].fr=u; edg1[tot].w=w; head1[u]=tot++;}int dis[MAXN],lca[MAXN],fa[MAXN];int find1(int a){ if(a==fa[a]) return a; else { int b=find1(fa[a]); return fa[a]=b; }}void tarjan(int u){ // printf("1"); vis[u]=1; fa[u]=u; for(int i=head1[u];i!=-1;i=edg1[i].next) { int v=edg1[i].to; if(vis[v]) lca[edg1[i].w]=find1(v); } for(int i=head[u];i!=-1;i=edg[i].next) { int v=edg[i].to; if(!vis[v]) { dis[v]=dis[u]+edg[i].w; tarjan(v); fa[v]=u; } }}int main(){ int t; scanf("%d",&t); while(t--) { int n,m; scanf("%d%d",&n,&m); memset(head,-1,sizeof(head)); cnt=0; for(int i=1;i
             
              <= m;i++) //离线算法 记录下这2个点查询的排名 { int a,b; scanf("%d%d",&a,&b); add1(a,b,i); add1(b,a,i); } dis[1]=0; tarjan(1); for(int i=0;i