树分治
点分治
点分治适合处理大规模的树上路径信息问题。
我们先随意选择一个节点作为根节点
在本题中,对于经过根节点
注意在清空 memset
,而应将之前占用过的
点分治过程中,每一层的所有递归过程合计对每个点处理一次,假设共递归
若我们 每次选择子树的重心作为根节点,可以保证递归层数最少,时间复杂度为
请注意在重新选择根节点之后一定要重新计算子树的大小,否则一点看似微小的改动就可能会使时间复杂度错误或正确性难以保证。
参考代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 |
|
由于这里查询的是树上距离为
参考代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 |
|
例题 3 Luogu P2664 树上游戏
一棵每个节点都给定颜色的树,定义
这道题很考验对点分治思想的理解和应用,适合作为点分治的难度较高的例题和练习题。
首先,我们需要想明白一个转化。题目定义
考虑到点分治过程中,我们只需要分别考虑统计:
- 子树中以当前根节点为端点的路径对根的贡献
- lca 为当前根节点的路径对子树内每个点的贡献
1 部分比较好办,由于点分治中,递归层数不超过
而针对 2 部分,设当前根节点
路径上出现过的颜色,数量设为 , 除了 以外的其他所有子树的总大小设为 , 那么这些出现过的颜色对 的答案贡献为 。 路径上没有出现过的颜色 ,它们的贡献来自于 除了 以外的其他所有子树的 ,这部分答案为 。
以上是全部统计思路,实现细节详见参考代码。
参考代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 |
|
边分治
与上面的点分治类似,我们选取一条边,把树尽量均匀地分成两部分(使边连接的两个子树的
但是这是不行的,考虑一个菊花图:
我们发现当一个点下有多个
如果这个图是个二叉树,就可以避免上面菊花图中应用边分治的弊端。因此我们考虑把一个多叉树转化成二叉树。
显然,我们只需像线段树那样建树就可以了。就像这样
新建出来的点根据题目要求给予恰当的信息即可。例如:统计路径长度时,将原边边权赋为
分析复杂度,发现最多会增加
几乎所有点分治的题边分都能做(常数上有差距,但是不卡),所以就不放例题了。
点分树
点分树是通过更改原树形态使树的层数变为稳定
常用于解决与树原形态无关的带修改问题。
算法分析
我们通过点分治每次找重心的方式来对原树进行重构。
将每次找到的重心与上一层的重心缔结父子关系,这样就可以形成一棵
由于树是
代码实现
有一个小技巧:每次用递归上一层的总大小
参考代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 |
|
本页面最近更新:2024/10/9 22:38:42,更新历史
发现错误?想一起完善? 在 GitHub 上编辑此页!
本页面贡献者:chenyanlann, ChungZH, dkz051, Early0v0, Enter-tainer, fanfansann, Henry-ZHR, hsfzLZH1, Ir1d, kenlig, ksyx, Marcythm, mcendu, megakite, ouuan, partychicken, shuzhouliu, shuzhouliu-bot, StudyingFather, thallium, Tiphereth-A, Xeonacid
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用