牛客网 桂林电子科技大学第三届ACM程序设计竞赛 D.寻找-树上LCA(树上a到b的路径上离c最近的点)

Mike

链接：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≤10

5
树上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[maxn<<1][25];//数组记得开2倍，因为遍历之后序列长度变为2*n-1
 32 bool vis[maxn];//标记
 33 
 34 struct node{
 35   int u,v,w,next;
 36 }edge[maxn<<1];
 37 
 38 int tot,head[maxn];//head保存的是以当前节点为起点的所有边中最后一条边的编号
 39 
 40 int num;
 41 
 42 inline void add(int u,int v,int w)
 43 {
 44   edge[num].u=u;edge[num].v=v;edge[num].w=w;//存边和权值
 45   edge[num].next=head[u];head[u]=num++;//next保存的是以u为起点的上一条边的编号
 46   u=u^v;v=u^v;u=u^v;//节点互换，存两次，因为为无向图，(u,v)存一次，(v,u)存一次，以下操作同上
 47   edge[num].u=u;edge[num].v=v;edge[num].w=w;
 48   edge[num].next=head[u];head[u]=num++;
 49 }
 50 
 51 int ver[maxn<<1],deep[maxn<<1],node[maxn<<1],dir[maxn<<1];
 52 //ver节点编号，dfs搜索过程中的序列，deep深度，node点编号位置，dir距离
 53 
 54 void dfs(int u,int dep)
 55 {
 56   vis[u]=true;//标记u节点被访问过
 57   ver[++tot]=u;//存dfs序
 58   node[u]=tot;//节点的dfs序的编号
 59   deep[tot]=dep;//该编号的深度
 60   for(int k=head[u];k!=-1;k=edge[k].next)//倒着遍历以u节点为起点的所有边的编号
 61   if(!vis[edge[k].v]){//如果该编号的边未被访问过
 62     int v=edge[k].v,w=edge[k].w;//v表示该边的终点，w表示该边的权值
 63     dir[v]=dir[u]+w;//权值和
 64     dfs(v,dep+1);//再往下dfsv节点的深度
 65     ver[++tot]=u;deep[tot]=dep;//表示dfs的时候还要回溯到上面，就是把dfs序保存一下，走到底再返回去去遍历没走过的点
 66   }
 67 }
 68 
 69 void ST(int n)//ST操作
 70 {
 71   for(int i=1;i<=n;i++)
 72     dp[i][0]=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[i][j-1],b=dp[i+(1<<(j-1))][j-1];
 76       dp[i][j]=deep[a]<deep[b]?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[l][k],b=dp[r-(1<<k)+1][k];//保存的是编号
 86   return deep[a]<deep[b]?a:b;
 87 }
 88 
 89 int LCA(int u,int v)
 90 {
 91   int x=node[u],y=node[v];
 92   if(x>y)swap(x,y);
 93   int res=RMQ(x,y);
 94   return ver[res];
 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[1]=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[A]+dir[c]-2*dir[lca];
128     if(minn>dis){
129       minn=dis;pos=A;
130     }
131     lca=LCA(B,c);
132     dis=dir[B]+dir[c]-2*dir[lca];
133     if(minn>dis){
134       minn=dis;pos=B;
135     }
136     lca=LCA(C,c);
137     dis=dir[C]+dir[c]-2*dir[lca];
138     if(minn>dis){
139       minn=dis;pos=C;
140     }
141     cout<<pos<<endl;
142   }
143   return 0;
144 }