牛客网 桂林电子科技大学第三届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≤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 ;
}
上一篇:Hadoop生态圈-Hive快速入门篇之Hive环境搭建


下一篇:华南师大 2017 年 ACM 程序设计竞赛新生初赛题解