【题目描述】
方方方种下了三棵树，一年后，第一棵树长出了n个节点。
方方方会向你提出m个询问，每个询问给出两个数i，j，你需要回答i号节点和j号节点在树上的距离。
【输入数据】
第一行两个整数n，m。接下来n-1行每行两个整数a，b表示一条边。接下来m行每行两个整数i，j表示询问。
【输出数据】
m行，每行一个整数表示答案。
【样例输入】
3 2
1 2
1 3
3 2
1 1
【样例输出】
2
0
【数据范围】
对于30%的数据，n,m<=1000。
对于100%的数据，n,m<=500000。
题解：啊mdzz写个LCA啊。。。A到B的距离不就是A到根节点，B到根节点的距离之和减去（LCA到根节点的距离的两倍），今天学了个比较有趣的LCA。。QAQ
传教时间到！
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 struct node 8 { 9 int from,to,next,val;10 }edge[2*500001];11 struct node112 {13 int from,to,next,num;14 }edge1[2*500001];15 int tol,head[500001],head1[500001],cnt1,father[500001],dis[500001],LCA[500001],n,m;16 bool visit[500001];17 void add(int a,int b,int c)18 {19 edge[tol].from=a;20 edge[tol].to=b;21 edge[tol].next=head[a];22 edge[tol].val=c;23 head[a]=tol++;24 }25 void add1(int a,int b,int c)26 {27 edge1[cnt1].from=a;28 edge1[cnt1].to=b;29 edge1[cnt1].next=head1[a];30 edge1[cnt1].num=c;31 head1[a]=cnt1++;32 }33 int find(int x)34 {35 if(x!=father[x])36 father[x]=find(father[x]);37 return father[x];38 }39 void tarjan(int u)40 {41 int j;42 visit[u]=1;43 father[u]=u;44 for(j=head1[u];j!=-1;j=edge1[j].next)45 {46 int temp=edge1[j].to;47 if (visit[temp])48 LCA[edge1[j].num]=find(temp);49 }50 for(j=head[u];j!=-1;j=edge[j].next)51 {52 int temp=edge[j].to;53 if(!visit[edge[j].to])54 {55 dis[temp]=dis[u]+edge[j].val;56 tarjan(temp);57 father[temp]=u;58 }59 }//xjb dfs...60 }61 int main()62 {63 int i,a,b;64 freopen("tree.in","r",stdin);65 freopen("tree.out","w",stdout);66 scanf("%d%d",&n,&m);67 tol=0,cnt1=0;68 memset(head,-1,sizeof(head));69 memset(visit,0,sizeof(visit));70 memset(head1,-1,sizeof(head1));71 for(i=1;i<=n-1;i++)72 {73 scanf("%d%d",&a,&b);74 add(a,b,1);75 add(b,a,1);76 }77 for(i=1;i<=m;i++)78 {79 scanf("%d%d",&a,&b);80 add1(a,b,i);81 add1(b,a,i);82 }83 dis[1]=0;84 tarjan(1);85 for(i=0;i<=cnt1-1;i+=2)86 printf("%d\n",dis[edge1[i].from]+dis[edge1[i].to]-2*dis[LCA[edge1[i].num]]);87 return 0;88 }
啊这个代码比较核心。。↓
1 int find(int x) 2 { 3 if (x!=father[x]) 4 father[x]=find(father[x]); 5 return x; 6 void tarjan(int u) 7 { 8 visit[u]=1; 9 father[u]=u;10 for (i=g2[u];i!=-1;i=e2[i].next)11 if (visit[e2[i].to])12 LCA[e2[i].num]=find(e2[i].to);13 for (i=g[u];i!=-1;i=e[i].next)14 {15 if (!visit[e[i].to])16 {17 dis[e[i].to]=dis[u]+e[i].w;18 tarjan(w[i].to);19 father[e[i].to]=u;20 }21 }22 23 } 啊今天只写过了第一题QAQ。。要完啊