建个微商城网站多少钱,网站主机服务器,wordpress 图片插件下载,在线生成个人网址https://www.luogu.com.cn/problem/CF1192B
对于直径的求法#xff0c;常用dp或两次dfs#xff0c;但如果要动态维护似乎都不太方面#xff0c;那么可以维护树上路径最大值。
树上路径为#xff1a; d e p u d e p v − 2 d e p l c a ( u , v ) dep_udep_v-2\times de…https://www.luogu.com.cn/problem/CF1192B
对于直径的求法常用dp或两次dfs但如果要动态维护似乎都不太方面那么可以维护树上路径最大值。
树上路径为 d e p u d e p v − 2 × d e p l c a ( u , v ) dep_udep_v-2\times dep_{lca(u,v)} depudepv−2×deplca(u,v)
为方便求 l c a ( u , v ) lca(u,v) lca(u,v)可以直接化为树上欧拉环游序任意 u , v u,v u,v 中必有 l c a ( u , v ) lca(u,v) lca(u,v) 而且 l c a ( u , v ) lca(u,v) lca(u,v) 必然为任意 u , v u,v u,v 中最浅的点 然后直接拿个线段树维护即可
总结
动态维护直径动态维护树上路径涉及LCA点转欧拉环游序对欧拉环游序用数据结构维护
