最近公共祖先问题~~
题目大意：一个村子里有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，里面讲的很不错！！
直接贴一下代码：
View Code 1 # include
2 # include 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
Tags:
延伸阅读
最新评论