动态维护直径 || 动态维护树上路径 || 涉及LCA点转序列 || 对欧拉环游序用数据结构维护：1192B
动态维护直径 || 动态维护树上路径 || 涉及LCA点转序列 || 对欧拉环游序用数据结构维护：1192B
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132566345
https://www.luogu.com.cn/problem/CF1192B
对于直径的求法，常用dp或两次dfs，但如果要动态维护似乎都不太方面，那么可以维护树上路径最大值。
树上路径为：
为方便求 ，可以直接化为树上欧拉环游序，任意 中必有 ，而且 必然为任意 中最浅的点
然后直接拿个线段树维护即可
总结：
-
动态维护直径
-
动态维护树上路径
-
涉及LCA点转欧拉环游序
-
对欧拉环游序用数据结构维护
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2021-11-16
【P2325 [SCOI2005]王室联邦】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15564095.html 题目链接 题目 “余”人国的国王想重新编制他的国家。他想把他的国家划分成若干个省，每个省都由他们王室联邦的一个成员来管理。 他的国家有 NNN 个城市，编号为 1…N1\ldots N1…N。 一些城市之间有道路相连，任意两个不同的城市之间有且仅有一条直接或间接的道路。 为了防止管理太过分散，每个省至少要有 BBB 个城市。 为了能有效的管理，每个省最多只有 3×B3\times B3×B 个城市。 每个省必须有一个省会...
2022-04-29
【CF339D Xenia and Bit Operations】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16207447.html 题目链接 题目 Xenia the beginner programmer has a sequence $ a $ , consisting of $ 2^{n} $ non-negative integers: $ a_{1},a_{2},…,a_{2^{n}} $ . Xenia is currently studying bit operations. To better understand how they ...
2021-11-24
【P1270 “访问”美术馆】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15600574.html 题目链接 典型的树形dp。 设 dp(x,i)dp(x, i)dp(x,i) 表示 xxx 的子树内逗留 iii 秒的作品最大值。 dp(x,i)=maxy∈xmaxi=0smaxj=2×zidp(y,j−2×z)−dp(x,j−i)dp(x, i)=\max_{y\in x}\max_{i=0}^s\max_{j=2\times z}^i dp(y,j-2\times z)-dp(x,j-i) dp(x,i)=y...
2023-11-08
树上移动类贪心：1108T4 / CF1381D
树上移动类贪心：1108T4 / CF1381D 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134297045 http://47.92.197.167:5283/contest/428/problem/4 我们定义关键点为有3条路径大于 ≥L\ge L≥L 的点。 如果其中一个点可以到达关键点，那么就可行。这是一个充要条件。 我们以关键点为根，如果某个时刻两个点一个是另一个是父亲，那么一定可以开到关键点那里。 我们只需要两个端点轮流往他们子树最深处的地...
2023-08-06
cqd分治思想
cqd分治思想 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132135114 https://www.luogu.com.cn/problem/P3810 常用于维护三维偏序问题，对于相等的情况处理我感觉不太好，之前ABC打cdq被制裁了 三维，第一维显然排序 分治，所以第二维很明显了。因为只需要考虑左对右的贡献，所以黑白染色一下，再按b排即可。然后黑白一个对应查询一个对应修改操作。 最后一个拿树状数组
2021-12-02
【[ARC063C] Integers on a Tree】
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15633812.html 题目链接 对于最小的点，与它相连的没填的点中，都赋值为这个点点权+1。 这样子贪心就算旁边的点必然会比这个点大，所以+1是没错的。 最后再遍历所有边检验答案合法性。 Code 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666...