BZOJ1787 meet
2024-08-28 09:19:41
题目:http://www.lydsy.com/JudgeOnline/problem.php?id=1787
水题,但是结论很有趣。
题目求的是距离三个点之和最小的点。
这个很显然是在三个LCA上,因为可以证明除LCA的点是由LCA移动来的,这个过程中
如果在 (x,y) 移动,答案不变没有意义。
如果偏离 (x,y) 移动,答案不优。
然而有一个好玩的结论:若有两个点对 LCA 相同那么答案为另一个 LCA
画画图就可以发现,x 与 y 到另一个 LCA 的路径有重合,很显然的吧。
#include <cstdio>
#include <cstring>
#include <algorithm> #define N 500010
#define p E[i].x using namespace std; struct edge{
int x,to;
}E[N<<]; int n,m,totE,g[N],fa[N][],d[N]; inline void addedge(int x,int y){
E[++totE]=(edge){y,g[x]}; g[x]=totE;
} void dfs(int x){
for(int i=;fa[x][i-]&&i<=;i++)
fa[x][i]=fa[fa[x][i-]][i-];
for(int i=g[x];i;i=E[i].to)
if(p!=fa[x][]){
fa[p][]=x;
d[p]=d[x]+;
dfs(p);
}
} int lca(int x,int y){
if(d[x]<d[y]) swap(x,y);
for(int i=;~i;i--)
if(d[fa[x][i]]>=d[y]) x=fa[x][i];
if(x==y) return x;
for(int i=;~i;i--)
if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
return fa[x][];
} int dist(int a,int b){
return d[a]+d[b]-*d[lca(a,b)];
} void ask(int a,int b,int c){
int f1=lca(a,b),f2=lca(a,c),f3=lca(b,c),ans,ansv;
if(f1==f2) ans=f3;
else if(f2==f3) ans=f1;
else ans=f2;
ansv=dist(a,ans)+dist(b,ans)+dist(c,ans);
printf("%d %d\n",ans,ansv);
} int main(){
scanf("%d%d",&n,&m);
for(int i=,x,y;i<n;i++){
scanf("%d%d",&x,&y);
addedge(x,y);
addedge(y,x);
}
d[]=;
dfs();
for(int i=,x,y,z;i<=m;i++){
scanf("%d%d%d",&x,&y,&z);
ask(x,y,z);
}
return ;
}
最新文章
- POJ3083Catch That Cow[BFS]
- TF Boys (TensorFlow Boys ) 养成记(二)
- 第十四章:高级I/O
- window下安装nodejs
- ls 命令详解
- Android中自定义ActionBar的背景色等样式style
- java.lang.OutOfMemoryError: GC overhead limit exceeded 问题分析和解决(转)
- malloc、calloc、realloc三者的差别
- VMware vSphere 服务器虚拟化之二十八 桌面虚拟化之安装View传输服务器
- document.getElementById(";searchForm";).submit is not a function
- NPOI office 组件资料汇总 (excel, word)
- 区块链 PoW 与 PoS 的纷争
- UNIX网络编程——ioctl 函数的用法详解
- [Android] Android RxJava2+Retrofit2+OkHttp3 的使用
- tablib cell() missing 1 required positional argument: &#39;column&#39; 报错
- 【转载】Hadoop 2.7.3 和Hbase 1.2.4安装教程
- Memcached深入分析及内存调优
- sql查看所有表大小的方法
- Frameset 两页面互调控件技术案例
- Quartz教程五:SimpleTrigger
热门文章
- 应用程序中的server错误,没有名称为“ServiceBehavior”的服务行为
- XP操作系统设置:[82]关机快捷键
- 老大写得一个非常高大上的Makefile,包括非常多语法:
- 使用BatteryHistorian分析和优化应用电量
- 基于jquery 全选、反选、各行换色、单击行选中事件实现代码
- iOS 把数据库文件打包到mainbundle中,查找不到路径的解决的方法;以及在删除bundle中文件的可行性
- wyh2000 and pupil
- UBUntu 软件 源配置方法
- 嵌入式开发之davinci--- 8148/8168/8127 中的添加算饭scd 场景检测 代码实现
- sql建表,建索引注意事项