传送门

解题思路

可以通过手玩或打表发现,其实要选的点一定是他们三个两两配对后其中一对的$lca$上,那么就直接算出来所有的$lca$,比较大小就行了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm> using namespace std;
const int MAXN = ; inline int rd(){
int x=,f=;char ch=getchar();
while(!isdigit(ch)) {f=ch=='-'?:;ch=getchar();}
while(isdigit(ch)) {x=(x<<)+(x<<)+ch-'';ch=getchar();}
return f?x:-x;
} int ans,p,n,m,head[MAXN],cnt,num;
int to[MAXN<<],nxt[MAXN<<];
int id[MAXN],dep[MAXN],top[MAXN],fa[MAXN],siz[MAXN],son[MAXN]; inline void add(int bg,int ed){
to[++cnt]=ed,nxt[cnt]=head[bg],head[bg]=cnt;
} void dfs1(int x,int f,int d){
dep[x]=d,fa[x]=f,siz[x]=;register int maxson=,u;
for(register int i=head[x];i;i=nxt[i]){
u=to[i];if(u==f) continue;
dfs1(u,x,d+);siz[x]+=siz[u];
if(siz[u]>maxson) {maxson=u;son[x]=u;}
}
} void dfs2(int x,int topf){
top[x]=topf;id[x]=++num;if(!son[x]) return;dfs2(son[x],topf);int u;
for(register int i=head[x];i;i=nxt[i]){
u=to[i];if(u==fa[x] || u==son[x]) continue;dfs2(u,u);
}
} inline int lca(int x,int y){
while(top[x]!=top[y]){
if(dep[top[x]]>dep[top[y]]) x=fa[top[x]];
else y=fa[top[y]];
}
return dep[x]>dep[y]?y:x;
} inline void LCA(int x,int y,int z){
register int tmp,dis,all;tmp=lca(x,y);all=lca(tmp,z);
dis=dep[x]+dep[y]-dep[tmp]+dep[z]-*dep[all];ans=dis;p=tmp;dis+=dep[tmp];
tmp=lca(x,z);dis-=dep[tmp];if(ans>dis) {ans=dis;p=tmp;}
dis+=dep[tmp];tmp=lca(y,z);dis-=dep[tmp];if(ans>dis) {ans=dis;p=tmp;}
} void out(int x){
if(!x) return;
out(x/);putchar(''+x%);
} int main(){
n=rd(),m=rd();int x,y,z;
for(register int i=;i<n;i++){
x=rd(),y=rd();add(x,y),add(y,x);
}
dfs1(,,),dfs2(,);
while(m--) {
x=rd(),y=rd(),z=rd();ans=1e9;
LCA(x,y,z);out(p);putchar(' ');if(!ans) putchar('');else out(ans);
putchar('\n');
}
return ;
}

最新文章

  1. atitit.404错误的排查流程总结
  2. Bootstrap3.0学习第十五轮(大屏幕介绍、页面标题、缩略图、警示框、Well)
  3. UI设计基础百科
  4. POJ 1062 昂贵的聘礼 最短路 难度:0
  5. God of War - HDU 2809(状态压缩+模拟)
  6. Qt生成灰度图(转载)
  7. 【Andrioid】在Gradle编译时生成一个不同的版本号,动态设置应用程序标题,应用程序图标,更换常数
  8. django框架简介
  9. TensorFlow(三)---------正则化
  10. MyBatis的关于批量数据操作的测试
  11. python requests库学习笔记(下)
  12. ECMA262,JavaScript引擎,浏览器
  13. springboot 错误求解决
  14. WebSocket 实现链接 发送消息
  15. Ubuntu16.04系统安装搜狗输入法详细教程(转载)
  16. EntityFramework Core问题处理集锦(一)
  17. jquery之商城菜单
  18. 【软件工程1916|W(福州大学)_助教博客】团队第四次作业(第7次)成绩公示
  19. ny106 背包问题
  20. STL容器与拷贝构造函数

热门文章

  1. AtCoder ABC 130F Minimum Bounding Box
  2. JS函数 函数调用 函数定义好后,是不能自动执行的,需要调用它,直接在需要的位置写函数名。
  3. XSS攻击原理
  4. spark安装及配置
  5. sysobjects syscolumns
  6. 关于 argc 和 argv
  7. 初识 HTML
  8. PHP跨服务器提交数据
  9. git使用过程中问题
  10. duilib教程之duilib入门简明教程18.其他