首页 > 编程语言 > 详细

倍增(lcm+java)

时间:2021-03-07 21:52:56      阅读:26      评论:0      收藏:0      [点我收藏+]

问题:求一个二叉树,x节点到y节点的距离

算法:找到xy最近的父节点,res=cent[x]+cent[y]-2*cent[lcm(x,y)]


class Node{
	int l;
	int r;
	int cent;
	int father;
}

static
int lcm(int u,int v) { while(u!=v) { if(node[u].cent>node[v].cent)u=node[u].father; else if(node[u].cent<node[v].cent)v=node[v].father; else { u=node[u].father; v=node[v].father; } } return u; }

 

倍增(lcm+java)

原文:https://www.cnblogs.com/ydcwp/p/14496465.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!