树的一些小技巧~

# 主要讲一些树上路径的一些性质 - ### 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 $$ #### 至于为什么有这个性质嘛。。。感性的写，然后认真对拍，发现并没有错误，于是先辈们就得出了这个性质（太强辣）。