链接：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≤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 //可以看以前写的RMQ(ST)的详解https://www.cnblogs.com/ZERO-/p/8456910.html 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 }