【BZOJ1787】[Ahoi2008]Meet 紧急集合

Description

Input

Output

Sample Input

6 4
1 2
2 3
2 4
4 5
5 6
4 5 6
6 3 1
2 4 4
6 6 6

Sample Output

5 2
2 5
4 1
6 0

HINT

题解:自己画画图就能看出来,对于询问(a,b,c),我们两两求出LCA,然后一定是选择深度最大的LCA作为集合点。就没有然后了

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn=500010;
int n,m,cnt;
int to[maxn<<1],next[maxn<<1],head[maxn],fa[maxn][22],dep[maxn];
void dfs(int x)
{
for(int i=head[x];i!=-1;i=next[i])
{
if(to[i]==fa[x][0]) continue;
fa[to[i]][0]=x,dep[to[i]]=dep[x]+1,dfs(to[i]);
}
}
void add(int a,int b)
{
to[cnt]=b,next[cnt]=head[a],head[a]=cnt++;
}
int lca(int a,int b)
{
if(dep[a]<dep[b]) swap(a,b);
int i;
for(i=19;i>=0;i--) if(dep[fa[a][i]]>=dep[b]) a=fa[a][i];
if(a==b) return a;
for(i=19;i>=0;i--) if(fa[a][i]!=fa[b][i]) a=fa[a][i],b=fa[b][i];
return fa[a][0];
}
int main()
{
scanf("%d%d",&n,&m);
int i,j,a,b,c,x,y,z;
memset(head,-1,sizeof(head));
for(i=1;i<n;i++)
{
scanf("%d%d",&a,&b);
add(a,b),add(b,a);
}
dep[1]=1,dfs(1);
for(j=1;(1<<j)<=n;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",&a,&b,&c);
x=lca(a,b),y=lca(b,c),z=lca(a,c);
if(dep[x]<dep[y]) swap(x,y);
if(dep[x]<dep[z]) swap(x,z);
if(dep[y]<dep[z]) swap(y,z);
printf("%d %d\n",x,dep[a]+dep[b]+dep[c]-2*dep[z]-dep[x]);
}
return 0;
}

最新文章

  1. zookeeper启动后没有相关进程
  2. HTML5本地缓存数据
  3. (转载)前端构建工具gulp使用
  4. How Tomcat Works(十三)
  5. linux 查看当前所在目录的全路径
  6. 常用SQL代码段
  7. javascript 向上滚动
  8. HER COFFEE夜场代金券【1折】_北京美食团购_360团购导航
  9. ueditor+asp.net异步提交,可以实现了,嘿嘿
  10. SQL点滴23—T-SQL中的除法
  11. 转-Tomcat 8 安装和配置、优化
  12. Eclipse之JSON导包
  13. 字符编码知识简介和iconv函数的简单使用
  14. 偏置-方差分解(Bias-Variance Decomposition)
  15. 【tool】VLC播放rtmp协议
  16. kernel笔记——内核编译与进程管理
  17. ionic3开发ios端
  18. LeetCode: Distinct Subsequences 解题报告
  19. 整理用js实现tab标签页
  20. bosondata/chrome-prerender: Render JavaScript-rendered page as HTML/PDF/mhtml/png/jpeg using headless Chrome

热门文章

  1. java-基于JavaMail的Java邮件发送
  2. LIBSVM使用方法及参数设置 主要参考了一些博客以及自己使用经验。
  3. jQuery实现点击单选按钮切换选中状态效果
  4. 后台测试常需要的htm样式
  5. 关于Unity中的碰撞检测和管理(2D)
  6. Linux ad7606 驱动
  7. Checked Exception &amp; Unchecked Exception
  8. 在windows下编译x264
  9. linux -- #!/bin/bash
  10. Spring-更多DI的知识