[文章目录]
Description
Y岛风景美丽宜人，气候温和，物产丰富。Y岛上有N个城市，有N-1条城市间的道路连接着它们。每一条道路都连接某两个城市。幸运的是，小可可通过这些道路可以走遍Y岛的所有城市。神奇的是，乘车经过每条道路所需要的费用都是一样的。小可可，小卡卡和小YY经常想聚会，每次聚会，他们都会选择一个城市，使得3个人到达这个城市的总费用最小。 由于他们计划中还会有很多次聚会，每次都选择一个地点是很烦人的事情，所以他们决定把这件事情交给你来完成。他们会提供给你地图以及若干次聚会前他们所处的位置，希望你为他们的每一次聚会选择一个合适的地点。N<=500000，M<=500000。
三个点只会有两个LCA--CKH
不存在两个点相遇然后两个点一起向另一个点走而不是一个点向两个点交点的情况。
那么只会是两个点相遇，然后另一个点走到其链上。考虑两种情况，在lca的子树中，不在lca的子树中。
如果不在子树中，三点相遇的点为lca。
如果在子树中，相遇的点为该点和两点的lca的较深的一个。
综上，就是两个lca中较深的一个。
求lca呗？？？（你丫RMQ&&LCA MLE了。。。害的我敲了遍倍增）
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 500010
using namespace std;
int n,m;
int head[N],to[N<<1],nxt[N<<1],cnt;
inline void add(int x,int y) {to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt;}
int deep[N],fa[N][20];
void dfs(int x,int pre)
{
deep[x]=deep[pre]+1; fa[x][0]=pre;
for(int i=head[x];i;i=nxt[i])
if(to[i]!=pre)
dfs(to[i],x);
}
inline int get_lca(int x,int y)
{
if(deep[x]<deep[y]) swap(x,y);
for(int i=19;~i;--i) if(deep[fa[x][i]]>=deep[y]) x=fa[x][i];
if(x==y) return x;
for(int i=19;~i;--i) if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
return fa[x][0];
}
inline int dis(int x,int y,int z,int anc)
{
int tmp=get_lca(x,anc),re=0;
re+=deep[x]+deep[anc]-(deep[tmp]<<1);
tmp=get_lca(y,anc);
re+=deep[y]+deep[anc]-(deep[tmp]<<1);
tmp=get_lca(z,anc);
re+=deep[z]+deep[anc]-(deep[tmp]<<1);
return re;
}
int main()
{
scanf("%d%d",&n,&m); int x,y;
for(int i=1;i<n;++i)
{
scanf("%d%d",&x,&y);
add(x,y); add(y,x);
}
dfs(1,0);
for(int i=1;i<=19;++i) for(int j=1;j<=n;++j) fa[j][i]=fa[fa[j][i-1]][i-1];
int z,anc1,anc2,anc3;
while(m--)
{
scanf("%d%d%d",&x,&y,&z);
anc1=get_lca(x,y); anc2=get_lca(y,z); anc3=get_lca(x,z);
if(deep[anc1]<deep[anc2]) anc1=anc2;
if(deep[anc1]<deep[anc3]) anc1=anc3;
printf("%d %d\n",anc1,dis(x,y,z,anc1));
}
return 0;
}