顺义便宜的建站公司,如何设计一个网页的快捷方式,建设银行个人网站个人客户,计算机网络技术 网站建设P3345 [ZJOI2015]幻想乡战略游戏
带修改带权重心 这是经典的树上寻找关键点的题目#xff0c;我们使用点分治处理这个问题#xff0c;因为点分治的特性#xff0c;就相当于在树上二分了。但是这与倍增不同#xff0c;倍增只是在链上二分#xff0c;而点分治则是在整棵树上…P3345 [ZJOI2015]幻想乡战略游戏
带修改带权重心 这是经典的树上寻找关键点的题目我们使用点分治处理这个问题因为点分治的特性就相当于在树上二分了。但是这与倍增不同倍增只是在链上二分而点分治则是在整棵树上二分。
然后我们考虑如何二分显然带权重心的位置和边权无关并且每次只需要寻找一个点的2sumvsumu2sum_vsum_u2sumvsumu那么重心一定在这个子树内部。也就是说有一个儿子的答案比当前点小那么重心就在这个子树内。我们可以维护3个变量。 sumdsumdsumd:表示当前分治范围内dud_udu的总和 sdv:sdv:sdv:表示当前分治范围内dudis(u,v)d_udis(u,v)dudis(u,v)的总和 sdvfsdvfsdvf表示当前分治范围内dudis(u,fav)d_udis(u,fa_v)dudis(u,fav)的总和
然后我们通过跳祖先节点容斥就可以计算出当前点作为重心的答案复杂度是O(logn)O(logn)O(logn)所以查询我们可以从根开始然后每次遍历所有儿子查询对应的答案找到答案最小的进入它所对应的子树然后继续这个过程知道所有儿子的答案都大于等于当前点答案那么就找到了重心。
然后我们考虑如何修改只会影响到当前点的所有祖先节点所以我们暴力跳祖先进行修改即可。然后这道题最好使用st表处理lca。
细节错误
一定要注意循环终止条件是f[i]!0相当于我们每次都是处理f[i]的有关信息处理的时候距离计算是dis(x,f[i])而不是dis(i,f[i])
