现在看来思路不是很难想啊…..但写起来像翔一样难受,细节这么多,拍一组改一组…..怪不得范老师在现场写挂了QAQ


分析

我们可以对区间询问\([l,r]\),用节点\(l-1\)和节点\(r+1\)去走,前者像\(lca\)走的过程中,记录路径上的右孩子,后者记录左孩子,那么得到的这些孩子,就是我们要的区间,具体的可以看一下下面这张图,从mls的视频中抠出来的

例如我们要查询的是黑竖线所包含的区间,那么蓝线就是走上去的路径,红色的点就是记录下的孩子,这些孩子就是要和\(u\)求距离的点

那么单点\(x\)和\(u\)的区里的求法就是\(d_x+d_u-2*d_{lca(x,u)}\)

显然,我们可以把所有的点合在一起做,即\(dist=\sum d_x+num_x*d_u-2*\sum d_{lca(u,x)}\)

\(\sum d_x+num_x*d_u-2\),我们可以通过\(O(n)\)大力预处理一波得到

那么最后一个怎么办,我们可以根据上图中黄线所连接的上端点成为悬挂点,我们可以通过\(lca(u,l-1)\)和\(lca(u,r+1)\)的深度把链分成两段,在\(lca\)先的所有端点的\(\sum d_{lca(u,x)}=num_x*d_lca\),,上半部分点的\(lca\)就是其悬挂点,则可以通过前面得到的预处理求得

还有最后一个问题是,\(l=1\)或者\(r=n\)的时候怎么办,大力特判一波

这道题目是一道完完整整的细节题啊QAQ

思路不难,调试起来还是有点略蛋疼啊…..

 

 


发表评论

电子邮件地址不会被公开。 必填项已用*标注