首页 > 代码库 > BZOJ 1787 AHOI2008 紧急集合 倍增LCA
BZOJ 1787 AHOI2008 紧急集合 倍增LCA
题目大意:给定一棵树,多次询问到三个点距离之和最小的点和距离
首先易知到两个点距离之和最小的点一定在两点间的路径上
于是到三个点距离之和最小的点一定在两两之间路径的交点上
然后很容易就会知道这个交点一定是其中两个点的LCA(其实是我不会证)
此外为什么不会是三个点共同的LCA呢?因为三个点共同的LCA一定是至少一对点的LCA 证明略(其实我也不会证)
然后就是枚举两两之间的LCA 求一下距离 取最小即可
然后就是倍增LCA的问题了 我的倍增LCA怎么又挂了 还能不能写对了0.0
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define M 500500 using namespace std; struct abcd{ int to,next; }table[M<<1]; int head[M],tot; int n,m,ans,anspoint; int dpt[M],fa[M][20]; void Add(int x,int y) { table[++tot].to=y; table[tot].next=head[x]; head[x]=tot; } void DFS(int x) { int i; dpt[x]=dpt[fa[x][0]]+1; for(i=head[x];i;i=table[i].next) { if(table[i].to==fa[x][0]) continue; fa[table[i].to][0]=x; DFS(table[i].to); } } int LCA(int x,int y) { int j; if(dpt[x]<dpt[y]) swap(x,y); for(j=19;~j;j--) if(dpt[fa[x][j]]>=dpt[y]) x=fa[x][j]; if(x==y) return x; for(j=19;~j;j--) if(fa[x][j]!=fa[y][j]) x=fa[x][j],y=fa[y][j]; return fa[x][0]; } inline int Distance(int x,int y) { return dpt[x]+dpt[y]-(dpt[LCA(x,y)]<<1); } void Query(int x,int y,int z) { int re=0; int lca=LCA(x,y); re+=dpt[x]-dpt[lca]; re+=dpt[y]-dpt[lca]; re+=Distance(lca,z); if(re<ans) ans=re,anspoint=lca; } int main() { int i,j,x,y,z; cin>>n>>m; for(i=1;i<n;i++) scanf("%d%d",&x,&y),Add(x,y),Add(y,x); DFS(1); for(j=1;j<=19;j++) for(i=1;i<=n;i++) fa[i][j]=fa[ fa[i][j-1] ][j-1]; for(i=1;i<=m;i++) { scanf("%d%d%d",&x,&y,&z); ans=0x3f3f3f3f; Query(x,y,z); Query(y,z,x); Query(z,x,y); printf("%d %d\n",anspoint,ans); } }
BZOJ 1787 AHOI2008 紧急集合 倍增LCA
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。