wordpress会务网站模版,雨发建设集团有限公司网站,游戏开科技怎么开,郴州网站建设软件定制开发平台欢迎访问~原文出处——博客园-zhouzhendong 去博客园看该题解 题目传送门 - BZOJ1787 题意概括 有一棵节点为n个(n≤500000)的树。接下来m次询问(m≤500000)#xff0c;每次给出3个点 a,b,c #xff0c;现在让你求一个点 p #xff0c;使得 dis(p,a) dis(p,b) dis(p,c) 最…欢迎访问~原文出处——博客园-zhouzhendong 去博客园看该题解 题目传送门 - BZOJ1787 题意概括 有一棵节点为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 cstring
#include algorithm
#include cstdio
#include cmath
#include cstdlib
using namespace std;
const int N5000005,MN*2;
struct Gragh{int cnt,y[M],nxt[M],fst[N];void set(){cnt0;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 i1;i20;i)anst[rt][i]anst[anst[rt][i-1]][i-1];for (int ig.fst[rt];i;ig.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 jdepth[b]-depth[a],i0;j0;j1,i)if (j1)banst[b][i];if (ab)return a;for (int i19;i0;i--)if (anst[a][i]!anst[b][i])aanst[a][i],banst[b][i];return anst[a][0];
}
int main(){scanf(%d%d,n,m);g.set();for (int i1,a,b;in;i){scanf(%d%d,a,b);g.add(a,b);g.add(b,a);}depth[0]-1;memset(anst,0,sizeof anst);dfs(0,1);for (int i1,a,b,c,ans,pos;im;i){scanf(%d%d%d,a,b,c);int p1LCA(a,b),p2LCA(a,c),p3LCA(b,c);if (p1p2)posp3;else if (p1p3)posp2;elseposp1;int q1LCA(pos,a),q2LCA(pos,b),q3LCA(pos,c);ansdepth[a]depth[b]depth[c]depth[pos]*3-depth[q1]*2-depth[q2]*2-depth[q3]*2;printf(%d %d\n,pos,ans);}return 0;
}转载于:https://www.cnblogs.com/zhouzhendong/p/BZOJ1787.html
