牛客网 桂林电子科技大学第三届ACM程序设计竞赛 D.寻找-树上LCA(树上a到b的路径上离c最近的点)
链接：https://ac.nowcoder.com/acm/contest/558/D来源：牛客网
寻找
小猫在研究树。
小猫在研究树上的距离。
给定一棵N个点的树，每条边边权为1。
Q次询问，每次给定a,b,c，请你输出a到b的路径上离c最近的点的编号。
输入描述:
第一行一个正整数N，表示节点数量。接下来N−1行，第i行两个正整数ui,vi，表示第i条边连接节点ui,vi。接下来一行一个正整数Q，表示询问数量。接下来Q行，每行三个正整数a,b,c，表示一组询问。
输出描述:
Q行，每行一个正整数，表示每个询问的答案。
示例1
输入
复制
5
1 2
1 3
2 4
2 5
3
1 2 3
4 5 1
1 4 5
输出
复制
1
2
2
备注:
1≤N,Q≤105
树上LCA,跑6个lca，然后特殊的a，b都是c的子节点这种情况特判一下就可以了。
代码:
1 //D
2 #include<iostream>
3 #include<cstdio>
4 #include<cstring>
5 #include<algorithm>
6 #include<bitset>
7 #include<cassert>
8 #include<cctype>
9 #include<cmath>
10 #include<cstdlib>
11 #include<ctime>
12 #include<deque>
13 #include<iomanip>
14 #include<list>
15 #include<map>
16 #include<queue>
17 #include<set>
18 #include<stack>
19 #include<vector>
20 using namespace std;
21 typedef long long ll;
22
23 const double PI=acos(-1.0);
24 const double eps=1e-6;
25 const ll mod=1e9+7;
26 const int inf=0x3f3f3f3f;
27 const int maxn=1e5+10;
28 const int maxm=100+10;
29 #define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
30
31 int dp;//数组记得开2倍，因为遍历之后序列长度变为2*n-1
32 bool vis;//标记
33
34 struct node{
35 int u,v,w,next;
36 }edge;
37
38 int tot,head;//head保存的是以当前节点为起点的所有边中最后一条边的编号
39
40 int num;
41
42 inline void add(int u,int v,int w)
43 {
44 edge.u=u;edge.v=v;edge.w=w;//存边和权值
45 edge.next=head;head=num++;//next保存的是以u为起点的上一条边的编号
46 u=u^v;v=u^v;u=u^v;//节点互换，存两次，因为为无向图，(u,v)存一次，(v,u)存一次，以下操作同上
47 edge.u=u;edge.v=v;edge.w=w;
48 edge.next=head;head=num++;
49 }
50
51 int ver,deep,node,dir;
52 //ver节点编号，dfs搜索过程中的序列，deep深度，node点编号位置，dir距离
53
54 void dfs(int u,int dep)
55 {
56 vis=true;//标记u节点被访问过
57 ver[++tot]=u;//存dfs序
58 node=tot;//节点的dfs序的编号
59 deep=dep;//该编号的深度
60 for(int k=head;k!=-1;k=edge.next)//倒着遍历以u节点为起点的所有边的编号
61 if(!vis.v]){//如果该编号的边未被访问过
62 int v=edge.v,w=edge.w;//v表示该边的终点，w表示该边的权值
63 dir=dir+w;//权值和
64 dfs(v,dep+1);//再往下dfsv节点的深度
65 ver[++tot]=u;deep=dep;//表示dfs的时候还要回溯到上面，就是把dfs序保存一下，走到底再返回去去遍历没走过的点
66 }
67 }
68
69 void ST(int n)//ST操作
70 {
71 for(int i=1;i<=n;i++)
72 dp=i;//初始化为自己
73 for(int j=1;(1<<j)<=n;j++){
74 for(int i=1;i+(1<<j)-1<=n;i++){
75 int a=dp,b=dp;
76 dp=deep<deep?a:b;
77 }
78 }
79 }
80
81 int RMQ(int l,int r)
82 {
83 int k=0;
84 while((1<<(k+1))<=r-l+1)k++;//最多能跳2的多少次幂
85 int a=dp,b=dp;//保存的是编号
86 return deep<deep?a:b;
87 }
88
89 int LCA(int u,int v)
90 {
91 int x=node,y=node;
92 if(x>y)swap(x,y);
93 int res=RMQ(x,y);
94 return ver;
95 }
96
97 int main()
98 {
99 int n,q;
100 num=0;
101 scanf("%d",&n);
102 memset(head,-1,sizeof(head));//初始化
103 memset(vis,false,sizeof(vis));
104 for(int i=1;i<n;i++){
105 int u,v,w;
106 scanf("%d%d",&u,&v);
107 w=1;
108 add(u,v,w);//存边
109 }
110 tot=0;
111 dir=0;
112 dfs(1,1);
113 ST(2*n-1);
114 cin>>q;
115 while(q--){
116 int a,b,c;
117 int minn=inf,pos;
118 scanf("%d%d%d",&a,&b,&c);
119 int A=LCA(a,b);
120 int B=LCA(a,c);
121 int C=LCA(b,c);
122 if(B==C) {
123 cout<<A<<endl;
124 continue;
125 }
126 int lca=LCA(A,c);
127 int dis=dir+dir-2*dir;
128 if(minn>dis){
129 minn=dis;pos=A;
130 }
131 lca=LCA(B,c);
132 dis=dir+dir-2*dir;
133 if(minn>dis){
134 minn=dis;pos=B;
135 }
136 lca=LCA(C,c);
137 dis=dir+dir-2*dir;
138 if(minn>dis){
139 minn=dis;pos=C;
140 }
141 cout<<pos<<endl;
142 }
143 return 0;
144 }
文档来源：51CTO技术博客https://blog.51cto.com/u_15310764/3167962
页:
[1]