codeforces #425 D. Misha, Grisha and Underground (dfs+rmq在线求LCA,讨论了一年)

题目链接

题意:

给出一棵树,以及三个点(可能重合),问两两组成的3条路径中,哪2条路径重合部分最长。

思路:

LCA还是一下就能想到的,rmq+dfs在线求。

然后我开始分情况讨论,讨论了一年也没讨论完,哭哭

结论是:求出三个lca,并取深度最大的那个,就是我们要的三岔路口K,然后分别求出K到a,b,c三点的路径长度,取最大值+1就是答案。

所以我的问题在于,没有试图往一般性的方向考虑,以为讨论一下就可以了…

这大概就是所谓的猜结论?

感性的理解的话,LCA越深,意味着另一个点到LCA的距离越远,也就是相交的路径越长

但是我的话,估计还是很难在短短不到一个小时内得出这样一般性的结论orz…

这大概就是数学方面的天赋差距把…T T

 

 

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz