改了一晚上bug，悲伤辣么大，明天再补详细题解

 

题解：

　　题目中说了无环的 也就是题目给的是一棵树或者是一片森林 通过加虚点可以把森林转化成为树 那么就是求树上任意2点之间的距离 2点之间的距离就是最近公共祖先分别这2个点的距离和 那么这个问题就被转化成了LCA问题。

　　（以上参考资料：）

　　对于是否在一个树上可以用并查集

　　在一个树上的用lca求公共祖先即可

坑：

　　在写这个程序的时候，踩了一些坑，害的我改了好久好久

　　①询问q次，for( )循环中的终止条件应该是 i <= q，而粗心的我却写成了 i <= m，然后，一直MLE.......

　　②在敲基于Tarjan的LCA的代码时，dfs( ) 过程中在两个for( )循环前应该有个fa[v] = f 语句，然额我并没加，又是一顿MLE.........

　　③基于二分的LCA：在查找u,v的LCA时，和书上的不同，借鉴的大神的代码%%%%%%%%，如果按照书上的敲，会TLE......

感想：

　　人太菜，大部分时间花费在debug上，呜呜呜~~~~~~~

AC代码献上：

代码1：基于二分的LCA

1 #include
      
         2 #include
       
          3 #include
        
           4 using namespace std;  5 #define pb(x) push_back(x)  6 const int maxn=1e4+50;  7   8 //======数据结构======  9 int n,m,q; 10 int max_dep; 11 int fa[20][maxn]; 12 int depth[maxn]; 13 int dist[maxn]; 14 struct Node 15 { 16     int to; 17     int weight; 18     Node(int to,int weight):to(to),weight(weight){} 19 }; 20 vector
         
          Edge[maxn]; 21 void addEdge(int u,int v,int w) 22 { 23     Edge[u].pb(Node(v,w)); 24     Edge[v].pb(Node(u,w)); 25 } 26 //==================== 27 //=======并查集======= 28 struct UnionSet 29 { 30     int fa[maxn]; 31     void Pretreat() 32     { 33         for(int i=1;i <= n;++i) 34             fa[i]=i; 35     } 36     int Find(int x) 37     { 38         return x == fa[x] ? x:fa[x]=Find(fa[x]); 39     } 40     void Union(int x,int y) 41     { 42         if((x=Find(x)) != (y=Find(y))) 43            fa[x]=y; 44     } 45 }; 46 UnionSet _set; 47 //==================== 48 //=========LCA======== 49 void Dfs(int v,int f,int d,int l) 50 { 51     max_dep=max(max_dep,d); 52     depth[v]=d; 53     dist[v]=l; 54     fa[0][v]=f; 55     for(int i=0;i < Edge[v].size();++i) 56     { 57         int to=Edge[v][i].to; 58         int weight=Edge[v][i].weight; 59         if(to != f) 60             Dfs(to,v,d+1,l+weight); 61     } 62 } 63 void Pretreat() 64 { 65     for(int k=0;k+1 < 20;++k) 66         for(int v=1;v <= n;++v) 67             if(fa[k][v] == -1) 68                 fa[k+1][v]=-1; 69             else 70                 fa[k+1][v]=fa[k][fa[k][v]]; 71 } 72 void Process() 73 { 74     for(int i=1;i <= n;++i) 75         if(!depth[i])//attention : the judgment condition is whether the value of depth[i] is equal 0 76             Dfs(i,-1,max_dep,0); 77     Pretreat(); 78 } 79 int LCA(int u,int v)//it faster than the method in book 80 { 81     if(depth[u] > depth[v]) 82         swap(u,v);//guarantee depth[v] > depth[u] 83     int i; 84     for(i=0;(1<
          
           <= depth[v];i++);//find the max k that v can << 85     i--; 86     for(int k=i;k >= 0;--k) 87         if((depth[v]-(1<
           
            = depth[u]) 88 v=fa[k][v]; 89 if(v == u) 90 return v; 91 for(int k=i;k >= 0;--k) 92 if(fa[k][v] != -1 && fa[k][v] != fa[k][u]) 93 { 94 u=fa[k][u]; 95 v=fa[k][v]; 96 } 97 return fa[0][v]; 98 } 99 //====================100 //========Query=======101 void Query()102 {103 for(int i=1;i <= q;i++)//bug : initial i < q write i < m,therefor return MLE104 {105 int u,v;106 scanf("%d%d",&u,&v);107 if(_set.Find(u) != _set.Find(v))108 printf("Not connected\n");109 else110 {111 int lca=LCA(u,v);112 printf("%d\n",dist[u]-dist[lca]+dist[v]-dist[lca]);113 }114 }115 }116 //========初始化======117 void Initial()118 {119 max_dep=0;120 _set.Pretreat();121 for(int i=1;i <= n;++i)122 {123 Edge[i].clear();124 dist[i]=0;125 depth[i]=0;126 }127 }128 void Read()129 {130 while(~scanf("%d%d%d",&n,&m,&q))131 {132 Initial();133 for(int i=1;i <= m;++i)134 {135 int u,v,w;136 scanf("%d%d%d",&u,&v,&w);137 addEdge(u,v,w);138 _set.Union(u,v);139 }140 Process();141 Query();142 }143 }144 //=====================145 int main()146 {147 Read();148 return 0;149 }
           
          
         
        
       
      

代码2：基于Tarjan的LCA

1 #include
      
         2 #include
       
          3 #include
        
           4 using namespace std;  5 const int maxn=1e4+50;  6   7 int n,m,q;  8 int dist[maxn];  9 int fa[maxn]; 10 int vis[maxn]; 11 int res[1000010]; 12 //==========链式前向星========== 13 struct Node1 14 { 15     int to; 16     int next; 17     int w; 18 }edge[2*maxn]; 19 int cntE; 20 int headE[maxn]; 21 void addEdge(int u,int v,int w) 22 { 23     edge[cntE].to=v; 24     edge[cntE].w=w; 25     edge[cntE].next=headE[u]; 26     headE[u]=cntE++; 27 } 28 struct Node2 29 { 30     int to; 31     int next; 32     int id; 33 }query[2000010]; 34 int cntQ; 35 int headQ[maxn]; 36 void addQuery(int u,int v,int id) 37 { 38     query[cntQ].to=v; 39     query[cntQ].id=id; 40     query[cntQ].next=headQ[u]; 41     headQ[u]=cntQ++; 42 } 43 void Init() 44 { 45     cntE=cntQ=0; 46     memset(headE,-1,sizeof headE); 47     memset(headQ,-1,sizeof headQ); 48 } 49 //============================== 50 //==========并查集============== 51 struct Unionset 52 { 53     int fa[maxn]; 54     void Pretreat() 55     { 56         for(int i=0;i < maxn;++i) 57             fa[i]=i; 58     } 59     int Find(int x) 60     { 61         return x == fa[x] ? x:fa[x]=Find(fa[x]); 62     } 63     void Union(int x,int y) 64     { 65         if((x=Find(x)) != (y=Find(y))) 66             fa[x]=y; 67     } 68 }_set; 69 //============================== 70 //==========LCA================= 71 int Find(int x) 72 { 73     return x == fa[x] ? x:fa[x]=Find(fa[x]); 74 } 75 void Dfs(int v,int f,int l) 76 { 77     vis[v]=true; 78     dist[v]=l; 79     fa[v]=v;//the oj will return MLE if don't add statement 80     for(int i=headE[v];~i;i=edge[i].next) 81     { 82         int to=edge[i].to; 83         int w=edge[i].w; 84         if(to != f) 85         { 86             Dfs(to,v,l+w); 87             fa[to]=v; 88         } 89     } 90     for(int i=headQ[v];~i;i=query[i].next) 91     { 92         int to=query[i].to; 93         int id=query[i].id; 94         if(vis[to] && _set.Find(to) == _set.Find(v)) 95             res[id]=dist[v]+dist[to]-2*dist[Find(to)]; 96     } 97 } 98 void Tarjan() 99 {100     for(int i=1;i <= n;++i)101         if(!vis[i])102             Dfs(i,i,0);103 }104 //==============================105 int main()106 {107     while(~scanf("%d%d%d",&n,&m,&q))108     {109         Init();110         _set.Pretreat();111         memset(vis,false,sizeof vis);112         memset(dist,0,sizeof dist);113         memset(res,-1,sizeof res);114         for(int i=1;i <= m;++i)115         {116             int u,v,w;117             scanf("%d%d%d",&u,&v,&w);118             addEdge(u,v,w);119             addEdge(v,u,w);120             _set.Union(u,v);121         }122         for(int i=1;i <= q;++i)123         {124             int u,v;125             scanf("%d%d",&u,&v);126             addQuery(u,v,i);127             addQuery(v,u,i);128         }129         Tarjan();130         for(int i=1;i <= q;++i)131             if(res[i] == -1)132                 printf("Not connected\n");133             else134                 printf("%d\n",res[i]);135     }136     return 0;137 }