题目: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 ;
}

最新文章

  1. POJ3083Catch That Cow[BFS]
  2. TF Boys (TensorFlow Boys ) 养成记(二)
  3. 第十四章:高级I/O
  4. window下安装nodejs
  5. ls 命令详解
  6. Android中自定义ActionBar的背景色等样式style
  7. java.lang.OutOfMemoryError: GC overhead limit exceeded 问题分析和解决(转)
  8. malloc、calloc、realloc三者的差别
  9. VMware vSphere 服务器虚拟化之二十八 桌面虚拟化之安装View传输服务器
  10. document.getElementById(&quot;searchForm&quot;).submit is not a function
  11. NPOI office 组件资料汇总 (excel, word)
  12. 区块链 PoW 与 PoS 的纷争
  13. UNIX网络编程——ioctl 函数的用法详解
  14. [Android] Android RxJava2+Retrofit2+OkHttp3 的使用
  15. tablib cell() missing 1 required positional argument: &#39;column&#39; 报错
  16. 【转载】Hadoop 2.7.3 和Hbase 1.2.4安装教程
  17. Memcached深入分析及内存调优
  18. sql查看所有表大小的方法
  19. Frameset 两页面互调控件技术案例
  20. Quartz教程五:SimpleTrigger

热门文章

  1. 应用程序中的server错误,没有名称为“ServiceBehavior”的服务行为
  2. XP操作系统设置:[82]关机快捷键
  3. 老大写得一个非常高大上的Makefile,包括非常多语法:
  4. 使用BatteryHistorian分析和优化应用电量
  5. 基于jquery 全选、反选、各行换色、单击行选中事件实现代码
  6. iOS 把数据库文件打包到mainbundle中,查找不到路径的解决的方法;以及在删除bundle中文件的可行性
  7. wyh2000 and pupil
  8. UBUntu 软件 源配置方法
  9. 嵌入式开发之davinci--- 8148/8168/8127 中的添加算饭scd 场景检测 代码实现
  10. sql建表,建索引注意事项