1787: [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

题解:求出两两lca,其中有两个相同,答案则为另一个,参考HZWer.

///

#include<bits/stdc++.h>
using namespace std;
//#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std ;
typedef long long ll;
#define mem(a) memset(a,0,sizeof(a))
#define pb push_back
inline ll read()
{
ll x=,f=;char ch=getchar();
while(ch<''||ch>''){
if(ch=='-')f=-;ch=getchar();
}
while(ch>=''&&ch<=''){
x=x*+ch-'';ch=getchar();
}return x*f;
}
//****************************************
const int N=;
#define mod 1000000007
#define inf 1000000007
int n,m,head[N],t,vis[N],deep[N],fa[N][];
struct ss {
int to,next;
}e[N*];
void add(int u,int v) {
e[t].next=head[u];e[t].to=v;head[u]=t++;
}
void init() {
t=;mem(head);mem(vis);mem(fa);mem(deep);
}
void dfs(int x) {
vis[x]=;
for (int i=; i<= ;i++) {
if(deep[x]<(<<i)) break;
fa[x][i] = fa[fa[x][i-]][i-];
}
for (int i=head[x];i;i=e[i].next) {
if(vis[e[i].to]) continue;
deep[e[i].to]=deep[x]+;
fa[e[i].to][]=x;
dfs(e[i].to);
}
}
int RMQ_LCA(int x,int y) {
if(deep[x]<deep[y]) swap(x,y);
int d=deep[x]-deep[y];
for (int i=; i<= ;i++)
if((<<i)&d) x=fa[x][i];
for (int i=; i>= ;i--) {
if(fa[x][i]!=fa[y][i]) {
x=fa[x][i];y=fa[y][i];
}
}
if(x==y) return x;
else return fa[x][];
}
int Dis_LCA(int x,int y) {
int LCA= RMQ_LCA(x,y);
return (deep[x]+deep[y]-*deep[LCA]);
}
int cal(int x,int y,int z) {
int A;
int L1=RMQ_LCA(x,y);
int L2=RMQ_LCA(y,z);
int L3=RMQ_LCA(x,z);
if(L1==L2) {
A=L3;
}
else if(L2==L3) {
A=L1;
}
else A=L2;
int anss=Dis_LCA(x,A)+Dis_LCA(y,A)+Dis_LCA(z,A);
printf("%d %d\n",A,anss);
//cout<<A<<" "<<anss<<endl;
}
int main() {
scanf("%d%d",&n,&m);
init();
for(int i=;i<n;i++) {
int u,v;
scanf("%d%d",&u,&v);
add(u,v);add(v,u);
}
dfs();
for(int i=;i<=m;i++) {
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
cal(a,b,c);
} return ;
}

代码

最新文章

  1. 手动编译并运行Java项目的过程
  2. 《Thinking in Java》十七章_容器深入研究_练习13(Page484)
  3. JS自动格式化输入的数字/千位分隔符VIEW:858
  4. 马化腾:办公用QQ休闲用微信[Dream Catchers论坛]
  5. hdu Interesting Fibonacci
  6. 在Ubuntu上为Android系统内置C可执行程序测试Linux内核驱动程序(老罗学习笔记2)
  7. 【Time系列五】个性时钟与秒表升级版
  8. stm32驱动DS1302芯片
  9. 使用ActionBar实现下拉式导航
  10. git fatal: I don&#39;t handle protocol &#39;https&#39;问题的解决
  11. 线性回归,附tensorflow实现
  12. 最重要的 Java EE 最佳实践
  13. Python中模块之logging &amp; subprocess的讲解
  14. Oracle数据安全解决方案(1)——透明数据加密TDE
  15. SQL反模式学习笔记21 SQL注入
  16. 手机端页面自适应解决方案—rem布局进阶版
  17. 用jsch.jar实现SFTP上传下载删除【转】【补】
  18. vue路由跳转的多种方式
  19. mysql自学路线
  20. window 后台执行 redis(隐藏窗口)

热门文章

  1. GitLab Runner and CICD
  2. Java继承体系中this的表示关系
  3. JQuery中常用的$.get(),$.post(),$.ajax(),$.getJSON(),load()的详解与区别
  4. android中TextView内容竖向显示
  5. H5 标签属性、input属性
  6. MyEclipse中VSS的使用详解
  7. (转)分布式文件存储FastDFS(二)FastDFS安装
  8. Android Binder机制(一) Binder的设计和框架
  9. Js—innerHTML和innerText的区别
  10. javaWEB中web.xml配置文件相关