首页 > 代码库 > 【bzoj1787】[Ahoi2008]Meet 紧急集合 倍增LCA
【bzoj1787】[Ahoi2008]Meet 紧急集合 倍增LCA
题目描述
输入
输出
样例输入
6 4
1 2
2 3
2 4
4 5
5 6
4 5 6
6 3 1
2 4 4
6 6 6
样例输出
5 2
2 5
4 1
6 0
题解
倍增LCA
首先有集合点必定在三点中两个点的LCA处,大概画一下就看出来了。
然后有x到y的距离为deep[x]+deep[y]-2*deep[lcaxy]
那么x、y、z三点到lcaxy的距离为deep[x]+deep[y]-2*deep[lcaxy]+deep[lcaxy]+deep[x]-deep[lcaxyz]
到lcaxz、lcayz同理。
可以看出集合点的选择只和deep[lca]有关,于是求一下最大值,再减掉就好了。
#include <cstdio> #include <algorithm> using namespace std; int head[500010] , to[1000010] , next[1000010] , cnt , log[500010] , fa[500010][21] , deep[500010]; void add(int x , int y) { to[++cnt] = y , next[cnt] = head[x] , head[x] = cnt; } void dfs(int x) { int i; for(i = 1 ; i <= log[deep[x]] ; i ++ ) fa[x][i] = fa[fa[x][i - 1]][i - 1]; for(i = head[x] ; i ; i = next[i]) if(to[i] != fa[x][0]) fa[to[i]][0] = x , deep[to[i]] = deep[x] + 1 , dfs(to[i]); } int getlca(int x , int y) { int i; if(deep[x] < deep[y]) swap(x , y); for(i = log[deep[x] - deep[y]] ; ~i ; i -- ) if(deep[x] - (1 << i) >= deep[y]) x = fa[x][i]; if(x == y) return x; for(i = log[deep[x]] ; ~i ; i -- ) if(fa[x][i] != fa[y][i]) x = fa[x][i] , y = fa[y][i]; return fa[x][0]; } int main() { int n , m , i , x , y , z , xy , xz , yz , t; scanf("%d%d" , &n , &m); for(i = 1 ; i < n ; i ++ ) scanf("%d%d" , &x , &y) , add(x , y) , add(y , x); for(i = 2 ; i <= n ; i ++ ) log[i] = log[i >> 1] + 1; dfs(1); while(m -- ) { scanf("%d%d%d" , &x , &y , &z); xy = getlca(x , y) , xz = getlca(x , z) , yz = getlca(y , z) , t = deep[x] + deep[y] + deep[z] - 2 * deep[getlca(xy , z)]; if(deep[xy] > deep[xz] && deep[xy] > deep[yz]) printf("%d %d\n" , xy , t - deep[xy]); else if(deep[xz] > deep[yz]) printf("%d %d\n" , xz , t - deep[xz]); else printf("%d %d\n" , yz , t - deep[yz]); } return 0; }
【bzoj1787】[Ahoi2008]Meet 紧急集合 倍增LCA
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。