链接：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的子节点这种情况特判一下就可以了。
代码:
//D
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<bitset>
#include<cassert>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<deque>
#include<iomanip>
#include<list>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<vector>
using namespace std;
typedef long long ll; const double PI=acos(-1.0);
const double eps=1e-;
const ll mod=1e9+;
const int inf=0x3f3f3f3f;
const int maxn=1e5+;
const int maxm=+;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); int dp[maxn<<][];//数组记得开2倍，因为遍历之后序列长度变为2*n-1
bool vis[maxn];//标记 struct node{
int u,v,w,next;
}edge[maxn<<]; int tot,head[maxn];//head保存的是以当前节点为起点的所有边中最后一条边的编号 int num; inline void add(int u,int v,int w)
{
edge[num].u=u;edge[num].v=v;edge[num].w=w;//存边和权值
edge[num].next=head[u];head[u]=num++;//next保存的是以u为起点的上一条边的编号
u=u^v;v=u^v;u=u^v;//节点互换，存两次，因为为无向图，(u,v)存一次，(v,u)存一次，以下操作同上
edge[num].u=u;edge[num].v=v;edge[num].w=w;
edge[num].next=head[u];head[u]=num++;
} int ver[maxn<<],deep[maxn<<],node[maxn<<],dir[maxn<<];
//ver节点编号，dfs搜索过程中的序列，deep深度，node点编号位置，dir距离 void dfs(int u,int dep)
{
vis[u]=true;//标记u节点被访问过
ver[++tot]=u;//存dfs序
node[u]=tot;//节点的dfs序的编号
deep[tot]=dep;//该编号的深度
for(int k=head[u];k!=-;k=edge[k].next)//倒着遍历以u节点为起点的所有边的编号
if(!vis[edge[k].v]){//如果该编号的边未被访问过
int v=edge[k].v,w=edge[k].w;//v表示该边的终点，w表示该边的权值
dir[v]=dir[u]+w;//权值和
dfs(v,dep+);//再往下dfsv节点的深度
ver[++tot]=u;deep[tot]=dep;//表示dfs的时候还要回溯到上面，就是把dfs序保存一下，走到底再返回去去遍历没走过的点
}
}
//可以看以前写的RMQ(ST)的详解https://www.cnblogs.com/ZERO-/p/8456910.html
void ST(int n)//ST操作
{
for(int i=;i<=n;i++)
dp[i][]=i;//初始化为自己
for(int j=;(<<j)<=n;j++){
for(int i=;i+(<<j)-<=n;i++){
int a=dp[i][j-],b=dp[i+(<<(j-))][j-];
dp[i][j]=deep[a]<deep[b]?a:b;
}
}
} int RMQ(int l,int r)
{
int k=;
while((<<(k+))<=r-l+)k++;//最多能跳2的多少次幂
int a=dp[l][k],b=dp[r-(<<k)+][k];//保存的是编号
return deep[a]<deep[b]?a:b;
} int LCA(int u,int v)
{
int x=node[u],y=node[v];
if(x>y)swap(x,y);
int res=RMQ(x,y);
return ver[res];
} int main()
{
int n,q;
num=;
scanf("%d",&n);
memset(head,-,sizeof(head));//初始化
memset(vis,false,sizeof(vis));
for(int i=;i<n;i++){
int u,v,w;
scanf("%d%d",&u,&v);
w=;
add(u,v,w);//存边
}
tot=;
dir[]=;
dfs(,);
ST(*n-);
cin>>q;
while(q--){
int a,b,c;
int minn=inf,pos;
scanf("%d%d%d",&a,&b,&c);
int A=LCA(a,b);
int B=LCA(a,c);
int C=LCA(b,c);
if(B==C) {
cout<<A<<endl;
continue;
}
int lca=LCA(A,c);
int dis=dir[A]+dir[c]-*dir[lca];
if(minn>dis){
minn=dis;pos=A;
}
lca=LCA(B,c);
dis=dir[B]+dir[c]-*dir[lca];
if(minn>dis){
minn=dis;pos=B;
}
lca=LCA(C,c);
dis=dir[C]+dir[c]-*dir[lca];
if(minn>dis){
minn=dis;pos=C;
}
cout<<pos<<endl;
}
return ;
}