Assignment 8 #1 乔卓然 1500011826.

Presentation on theme: "Assignment 8 #1 乔卓然 1500011826."— Presentation transcript:

1 Assignment 8 #1 乔卓然

2 375D. Tree and Queries 分治算法+启发式合并+离线处理+dfs优化+模拟递归

3 把问题分成两部分 对于已知的颜色信息： 用color数组维护每个节点的颜色 用cnt数组维护每个颜色的数目
用sum数组维护每个颜色数目对应的颜色的数目 每更新一个节点，有 cnt[color[x]]+=1 sum[cnt[color[x]]]+=1 更新的时间复杂度（O（1））

4 获取子树的颜色信息 先离线处理询问，按节点进行分类，避免重复遍历 暴力做法：对于每个节点，dfs其子树，求出答案 复杂度O（n^2）

5 两种不暴力但py必然超时的做法： 1.启发式合并(树上dp)，对每个节点维护平衡二叉树，计算其子树后进行合并，维护cnt值，合并总复杂度O（N(lg(N))^2），编程复杂度非常大 2.分块算法，dfs将树处理为数组，之后将数组分成sqrt（N）块，询问按在块内的左端点进行排序，块内暴力处理。时间复杂度O（N*sqrt(N)）

6 更高效的算法： 参考了sy2006的代码 只使用一个数组维护答案，对树的轻重链进行剖分，计算完所有子节点后回溯到父节点，保留子树大小最大的子节点的信息，暴力合并较小子节点的信息 暴力合并之前，预先用dfs将树压平，避免递归耗时 时间复杂度O(lg(N)*N) 用PyPy优化编译

7

8 But…… 解决办法：用栈模拟dfs和递归，判断入口和出口

9

10

11

12 However…… 考虑到多数竞赛会给python2-3倍的时间，在gym里调整时间测试了一下。 勉强可以接受。

13

14 使用文件输入输出，否则RTE stdin.readline()和stdin.writelines()方法 二叉树做法：记录元素标号，每次删除元素并插入根节点，时间复杂度O（nlogn），常数较大 树状数组 功能：在log(N)时间内求得前缀和

15

16

17 仍然调整了时间上限…… 可能还有改进空间。

18 Thanks