柒葉灬 的博客

柒葉灬 的博客

树的一些小技巧~

posted on 2018-08-21 22:17:24 | under 技巧篇 |

主要讲一些树上路径的一些性质

  • 1,最简单的,求 2 个点(x,y)之间路径的距离。

    我们可以用点到根的距离来转化,可以发现当dis[ x ] + dis [ y ] 时,根到 lca ( x , y ) 的距离多算了2次,所以减掉就可以了。

    $$ path\_dis(x,y)=dis[x]+dis[y]-2*dis[lca(x,y)] $$

怎么说,这应该是树上的最最最基础的知识吧,但是这种把距离压缩成点到根的距离这种思想很重要,很多题目直接算不好算,但是全部放到点到根的距离,再减掉重复的,就很简单了。


  • 2,其次,点到路径的距离很重要,要熟背!

    比如说点a到path(x,y)的距离记为dist(a,x,y)

    $$dist(a,x,y)= dis[a] + dis[lca(x,y)] - dis[lca(a,x)] - dis[lca(a,y)];$$

这个其实是由二个式子捏合而成,最朴素的求距离的方法是选x,y中深度最大的,然后求lca,最后求这个lca到a的距离,而上面给出的公式可以完美地融合这 2 种情况(证明略)


  • 3,最后,路径与路径之间还有个性质,即其中一条路径两端点的lca在另一条路径上。

    比如说有2条路径 path(x1,y1) 和 path(x2,y2) 则一定满足其中以下条件之一:

    $$ dist(lca(x1,y1),x2,y2)==0 $$ $$ dist(lca(x2,y2),x1,y1)==0 $$

至于为什么有这个性质嘛。。。感性的写,然后认真对拍,发现并没有错误,于是先辈们就得出了这个性质(太强辣)。