欢迎访问~原文出处——
题意概括
有一棵节点为n个(n≤500000)的树。接下来m次询问(m≤500000)，每次给出3个点 a,b,c ，现在让你求一个点 p ，使得 dis(p,a) + dis(p,b) + dis(p,c) 最小。
输出 p 和 dis(p,a) + dis(p,b) + dis(p,c)。
题解
分别求3个LCA。
学习LCA ->
有两个一样的，那么另外一个就是答案。
代码
#pragma comment(linker,"/STACK:1024000000,1024000000")#include#include #include #include #include using namespace std;const int N=500000+5,M=N*2;struct Gragh{ int cnt,y[M],nxt[M],fst[N]; void set(){ cnt=0; memset(fst,0,sizeof fst); } void add(int a,int b){ y[++cnt]=b,nxt[cnt]=fst[a],fst[a]=cnt; }}g;int n,m,depth[N],anst[N][20];void dfs(int prep,int rt){ depth[rt]=depth[anst[rt][0]=prep]+1; for (int i=1;i<20;i++) anst[rt][i]=anst[anst[rt][i-1]][i-1]; for (int i=g.fst[rt];i;i=g.nxt[i]) if (g.y[i]!=prep) dfs(rt,g.y[i]);}int LCA(int a,int b){ if (depth[a]>depth[b]) swap(a,b); for (int j=depth[b]-depth[a],i=0;j>0;j>>=1,i++) if (j&1) b=anst[b][i]; if (a==b) return a; for (int i=19;i>=0;i--) if (anst[a][i]!=anst[b][i]) a=anst[a][i],b=anst[b][i]; return anst[a][0];}int main(){ scanf("%d%d",&n,&m); g.set(); for (int i=1,a,b;i