題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=2586
?
最近公共祖先問題~~LAC離散算法
題目大意：一個村子里有n個房子，這n個房子用n-1條路連接起來，接下了有m次詢問，每次詢問兩個房子a,b之間的距離是多少。
很明顯的最近公共祖先問題，先建一棵樹，然后求出每一點i到樹根的距離dis[i],然后每次詢問a，b之間的距離=dis[a]+dis[b]-2*dis[LCA(a,b)];
LCA(a,b)即是a，b的最近公共祖先。。
關于最近公共祖先，給大家推薦一個學長的博客http://www.cnblogs.com/ylfdrib/archive/2010/11/03/1867901.html，里面講的很不錯！！
?
1 # include<stdio.h> 2 # include<string.h> 3 # define N 40005 4 # define M 205 5 struct node{ 6 int from,to,next,val; 7 }edge[2*N]; 8 struct node1{ 9 int from,to,next,num; 10 }edge1[2*M]; 11 int tol,head[N],head1[N],tol1,father[N],dis[N],LCA[M],n,m; 12 bool visit[N]; 13 void add(int a,int b,int c) 14 { 15 edge[tol].from=a;edge[tol].to=b;edge[tol].next=head[a];edge[tol].val=c;head[a]=tol++; 16 } 17 void add1(int a,int b,int c) 18 { 19 edge1[tol1].from=a;edge1[tol1].to=b;edge1[tol1].next=head1[a];edge1[tol1].num=c;head1[a]=tol1++; 20 } 21 int find(int x) 22 { 23 if(x!=father[x]) 24 father[x]=find(father[x]); 25 return father[x]; 26 } 27 void tarjan(int u) 28 { 29 int j,v; 30 visit[u]=1; 31 father[u]=u; 32 // 33 for(j=head1[u];j!=-1;j=edge1[j].next) 34 { 35 v=edge1[j].to; 36 if(visit[v]) LCA[edge1[j].num]=find(v); 37 } 38 // 39 for(j=head[u];j!=-1;j=edge[j].next) 40 { 41 v=edge[j].to; 42 if(!visit[v]) 43 { 44 dis[v]=dis[u]+edge[j].val; 45 tarjan(v); 46 father[v]=u; 47 } 48 } 49 } 50 int main() 51 { 52 int i,ncase,a,b,c; 53 scanf("%d",&ncase); 54 while(ncase--) 55 { 56 scanf("%d%d",&n,&m); 57 tol=0; 58 memset(head,-1,sizeof(head)); 59 for(i=1;i<n;i++) 60 { 61 scanf("%d%d%d",&a,&b,&c); 62 add(a,b,c); 63 add(b,a,c); 64 } 65 memset(visit,0,sizeof(visit)); 66 tol1=0; 67 memset(head1,-1,sizeof(head1)); 68 for(i=1;i<=m;i++) 69 { 70 scanf("%d%d",&a,&b); 71 add1(a,b,i); 72 add1(b,a,i); 73 } 74 ///LCA是一種離線算法，所以剛開始需要把所有的詢問都輸入，然后用鄰接表進行存儲，i表示第i次詢問 75 dis[1]=0; 76 tarjan(1); 77 for(i=0;i<tol1;i+=2) 78 { 79 a=edge1[i].from; 80 b=edge1[i].to; 81 c=edge1[i].num; 82 printf("%d\n",dis[a]+dis[b]-2*dis[LCA[c]]); 83 } 84 } 85 return 0; 86 }
?
**************************
?
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <vector> 5 using namespace std; 6 7 const int NN=50010; 8 9 int n,m; 10 vector<pair<int,int> > edge[NN],qe[NN]; 11 vector<int> q1,q2; 12 13 int p[NN]; 14 int find(int x) 15 { 16 if (p[x]!=x) p[x]=find(p[x]); 17 return p[x]; 18 } 19 20 int sum=0,ans[NN],dis[NN]; 21 bool vis[NN]={0}; 22 void lca(int u,int fa) 23 { 24 p[u]=u; 25 for (int i=0; i<edge[u].size(); i++) 26 { 27 int v=edge[u][i].first; 28 if (v==fa) continue; 29 dis[v]=dis[u]+edge[u][i].second; 30 lca(v,u); 31 p[v]=u; 32 } 33 vis[u]=true; 34 if (sum==m) return; 35 for (int i=0; i<qe[u].size(); i++) 36 { 37 int v=qe[u][i].first; 38 if (vis[v]) 39 ans[qe[u][i].second]=dis[u]+dis[v]-2*dis[find(v)]; 40 } 41 } 42 43 int main() 44 { 45 int u,v,w; 46 47 int t; 48 scanf("%d",&t); 49 while(t--){ 50 scanf("%d%d",&n,&m); 51 for (int i=1; i<=n; i++) 52 { 53 edge[i].clear(); 54 } 55 for (int i=1; i<n; i++) 56 { 57 scanf("%d%d%d",&u,&v,&w); 58 edge[u].push_back(make_pair(v,w)); 59 edge[v].push_back(make_pair(u,w)); 60 } 61 62 for (int i=0; i<m; i++) 63 { 64 scanf("%d%d",&u,&v); 65 qe[u].push_back(make_pair(v,i)); 66 qe[v].push_back(make_pair(u,i)); 67 ans[i]=0; 68 } 69 dis[1]=0; 70 lca(1,0); 71 for (int i=0; i<m; i++) printf("%d\n",ans[i]); 72 } 73 return 0; 74 }
?
