面试 线程 Markdown编辑器 ISP server chartjs 郑州小程序公司 php零基础入门视频 jq获取元素宽度 nginx默认端口号 mysql降序 查看oracle连接数 python刷题 wps文件修复工具下载 python开发教程 python调用方法 python或运算 python包 python简易教程 python参数 java集成 javafinally java数据库 java多线程教程 linux命令行 linuxshell编程 java网络编程 ip隐藏 不寻常的指南针 福昕阅读器绿色版 3389扫描器 getelementbyid 滑动门代码 pdf安装包官方下载 ps蒙版抠图详细教程 xapk安装器 t470拆机 cdr字体加粗 平原门下客三千 安卓游戏辅助
当前位置: 首页 > 学习教程  > 编程语言

CF1254D 题解总结

2020/11/4 15:05:03 文章标签:

文章目录SolutionSubtask 1: n,q≤5000n,q≤5000n,q≤5000Subtask 2: n,q≤105n, q≤10^5n,q≤105, 每个节点的度数不超过101010Subtask 3: n,q≤105n,q≤10^5n,q≤105, 无特殊限制Subtask 4: n,q≤5105n, q≤510^5n,q≤5105,无特殊限制Code总结⌊\lfloor⌊ 从朴素到…

⌊ \lfloor 从朴素到根号分治,从根号分治到树剖 ⌉ \rceil

Div.1 D的神仙题 😃

Solution

Subtask 1: n , q ≤ 5000 n,q≤5000 n,q5000

对于一次操作,我们分别处理树上的每个节点。定义 f u , v f_{u,v} fu,v表示将 u u u这个节点删去后,树上分裂出的子树中,包含 v v v的那颗子树的大小。

根据期望的定义,珂以发现对于一个节点 u u u,它的期望点权增长了 n − f ( v , u ) n \frac {n-f(v,u)} n nnf(v,u)。换句话说,如果 u u u r r r在同一棵子树中,那么就无法满足要求,否则就满足要求。

大概推一下式子,我们可以只处理 f u , v f_{u,v} fu,v的问题,对于前面的 n − n- n,我们可以在询问的时候用之前操作的次数乘上 n n n来减去一下,对于分母,我们可以在询问的时候乘上一个 n n n的逆元。

对于每一次操作,我们分别对每一个节点的期望点权进行修改;询问的时候 O ( 1 ) O(1) O(1)查询即可。时间复杂度 O ( q n ) O(qn) O(qn)

Subtask 2: n , q ≤ 1 0 5 n, q≤10^5 n,q105, 每个节点的度数不超过 10 10 10

此时,我们可以使用 d f s dfs dfs序套树状数组维护差分大力维护子树的修改操作。

由于每个节点的度数不超过 10 10 10,时间复杂度是 O ( q × 10 l o g n ) O(q×10logn) O(q×10logn)

Subtask 3: n , q ≤ 1 0 5 n,q≤10^5 n,q105, 无特殊限制

可以发现,这个思路本身已经无法优化了,也很难通过换用更高级的数据结构来维护。此时,我们观察一下 S u b t a s k   1 Subtask\ 1 Subtask 1中的思路,可以发现,一次操作的代价远远高于一次询问的代价,导致两个复杂度严重不平均。现在,我们要套路地牺牲查询的复杂度来降低操作的复杂度,使得这两种复杂度大致平均

我们仍然使用 d f s dfs dfs序套树状数组维护差分来搞。但是,如果一个节点的度数过多,而每次操作的都是这个节点,那不就完了……我们必须要优化这一步骤。即,如果操作的 v v v是一个度数超过 n \sqrt n n 的节点,直接 O ( 1 ) O(1) O(1)打上一个标记;如果度数不超过,就直接修改。对于一次查询,我们还要关注一下所有度数过大的节点的标记,否则无法正确求出这个节点的期望点权。

为什么这个算法的时间复杂度是正确的呢?因为,度数超过 n \sqrt n n 的节点级别为 n \sqrt n n 个,每次询问的复杂度是 O ( n ) O(\sqrt n) O(n )。对于一次修改,我们仍然采用原来的方法。

最劣情况的时间复杂度是 O ( n n l o g n ) O(n \sqrt {n log n}) O(nnlogn )。根号分治牛逼!

Subtask 4: n , q ≤ 5 × 1 0 5 n, q≤5×10^5 n,q5×105,无特殊限制

我们采用根号分治优化了暴力解法。现在,我们考虑换一种思想——使用树剖来优化到 O ( q l o g n ) O(qlogn) O(qlogn)

众所周知,我们在学树剖的时候,了解到了一个神奇的性质: ⌊ \lfloor 一个节点往上跳链的时候,跳到的轻儿子的个数不会超过 log ⁡ n \log n logn ⌉ \rceil

大概证明一下:

可以发现:对于一个节点 i i i的所有孩子的子树大小 s i z e s o n size_{son} sizeson中,如果存在一个 s i z e s o n ≥ n / 2 size_{son}≥n/2 sizesonn/2,那么这个孩子节点就一定是重孩子。

所以,所有轻儿子的子树大小不会超过其父亲节点的子树大小的一半;即,若从一个节点向下走,每走过一个轻儿子子树大小就会至少除以 2 2 2;所以,最多经过了 log ⁡ n \log n logn条轻边,那么往上跳链同理最多只会有 log ⁡ n \log n logn条重链。

所以树剖的复杂度是 O ( log ⁡ n ) O(\log n) O(logn)

证毕。


我们考虑这么干:对于一次操作,我们将它的重儿子做区间修改,对它的外子树作一次区间修改,其他的区间修改啥也别做。同时,在这个节点自己这里打上一个标记。

对于一次查询,可以发现,一个节点的一些贡献没有被累加,是因为它对于一些祖先,属于轻儿子的子树。我们采用树剖的思想向上跳链,由于一条重链的链头是轻儿子,那么我们就累加一下链头的父节点的标记即可。

可以发现,此时我们只需要区间修改与单点查询(询问的时候,查询一个节点在一个祖先的重儿子的子树中的贡献),仍然可以采用 d f s dfs dfs序套树状数组维护差分来维护一下。

放几张图:

在这里插入图片描述
这里红色的节点是一次操作中的参数 v v v

我们要对这些子树/外子树进行区间修改,即被标绿的部分:

在这里插入图片描述
对于一次查询,

在这里插入图片描述
根据树剖的时间复杂度,本题的总时间复杂度是 O ( q l o g n ) O(qlogn) O(qlogn)。本题得到完美解决。

树剖牛逼!

Code

咕咕咕

总结

⌊ \lfloor 从朴素到根号分治,从根号分治到树剖 ⌉ \rceil

可以说,这是一道大套路题,需要你的积累。你会就是会,你不会就是不会。

妙哉!


本文链接: http://www.dtmao.cc/news_show_350318.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?