zcmimi's blog

arrow_back欧拉序共1篇文章

avatar
zc
2020-09-08 07:47:00
查看原题

点击跳转

线段树维护动态直径

考虑设A_x为每个点的深度

答案可以写成这样的形式:

ans=\max_{1\le x<y\le n}\{ A_x + A_y - 2A_{\text{lca}(x,y)} \}

考虑欧拉序

因为边权为正,且欧拉序,那么

ans=\max_{1\le x<z<y\le n}\{ A_x + A_y - 2A_z \}

线段树维护区间内的min,max,sl,sr,s

其中min为区间最小值,max为区间最大值

sl_x=\max_{l<i<j<r} \{ A_i-2A_j \}\\ sr_x=\max_{l<i<j<r} \{ A_j-2A_i \}\\ s_x=\max_{l<i<k<j<r} \{ A_i+A_j-2A_k \}

最终答案就是s_1

修改边权可转化为子树(区间)加

1/1
Search
search