Assignment 8 #1 乔卓然 1500011826
375D. Tree and Queries 分治算法+启发式合并+离线处理+dfs优化+模拟递归
把问题分成两部分 对于已知的颜色信息: 用color数组维护每个节点的颜色 用cnt数组维护每个颜色的数目 用sum数组维护每个颜色数目对应的颜色的数目 每更新一个节点,有 cnt[color[x]]+=1 sum[cnt[color[x]]]+=1 更新的时间复杂度(O(1))
获取子树的颜色信息 先离线处理询问,按节点进行分类,避免重复遍历 暴力做法:对于每个节点,dfs其子树,求出答案 复杂度O(n^2)
两种不暴力但py必然超时的做法: 1.启发式合并(树上dp),对每个节点维护平衡二叉树,计算其子树后进行合并,维护cnt值,合并总复杂度O(N(lg(N))^2),编程复杂度非常大 2.分块算法,dfs将树处理为数组,之后将数组分成sqrt(N)块,询问按在块内的左端点进行排序,块内暴力处理。时间复杂度O(N*sqrt(N))
更高效的算法: 参考了sy2006的代码 只使用一个数组维护答案,对树的轻重链进行剖分,计算完所有子节点后回溯到父节点,保留子树大小最大的子节点的信息,暴力合并较小子节点的信息 暴力合并之前,预先用dfs将树压平,避免递归耗时 时间复杂度O(lg(N)*N) 用PyPy优化编译
But…… 解决办法:用栈模拟dfs和递归,判断入口和出口
However…… 考虑到多数竞赛会给python2-3倍的时间,在gym里调整时间测试了一下。 勉强可以接受。
使用文件输入输出,否则RTE stdin.readline()和stdin.writelines()方法 二叉树做法:记录元素标号,每次删除元素并插入根节点,时间复杂度O(nlogn),常数较大 树状数组 功能:在log(N)时间内求得前缀和
仍然调整了时间上限…… 可能还有改进空间。
Thanks