2144: 跳跳棋

求lca神题。

手推一下会发现,对于一个点,有三种跳法:

即中间点向两边跳,两边点向中间跳。

设三元组(u,v,w)(u < v < w).

设a  = v - u,b = u - v.

不难发现,若 a < b ,则只能u向后跳,反之w向前跳。

令向内跳的点为其父亲,向外跳的点为其儿子,那么此题即转换为了求树上两点的距离。

首先判断两点是否在同一个树上,即树根是否一样。

接下来可采用二分求两点到lca的距离。

求树上跳的步数,不可能一步步的跳,不难发现若a  < b,跳一步后得到(v,u + a,w) == (u + a,v + a,w).

那么跳k步有 (u + a*k,v + a*k,w); ( a < b && u + a*k < w && v + a*k < w)

另外若u == v则说明此时的(u,v,w)为根(因为跳不了了)

ps:这竟然是考试题的第一题。。。爆搜15分走人

c++代码如下:

 

3 + 7 =