C/C++教程

CF718D Andrew and Chemistry

本文主要是介绍CF718D Andrew and Chemistry,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

给你一个有 \(n\) 个点的树。当每一个点的度不超过 \(4\) 时这棵树是合法的。现在让你再添加一个点,在树仍然合法的情况下,一共有多少种树。
当两棵树同构时视作同一种。
保证输入的树是合法的。
\(n \le 10^5\)


  换根 DP 动态规划 树哈希

  学习 xzz 的树哈希做法。

  考虑将新加入的点作为根,那么可以转化为有根树的 HASH。

  也就是求所有度数 \(< 4\) 的点的哈希值的种类数。

  现在大部分题解可以直接 map + 记忆化搜索,然后复杂度是 \(\mathcal O(n\max\{deg_i\} \log n)\) 的,因为保证度数 \(\le 4\),于是可以通过。

  但是完全可以不限制度数的。

  对于树哈希,目前有很多种写法,但是感觉 xzz 讲的还是最好记忆并且被卡概率比较小的。

  因为括号序列可以很好地表示一颗树,于是我们可以考虑用字符串 HASH 维护整个树的括号序列,同时,为了消除子树之间顺序的影响,我们可以将其所有节点排序按照该节点为根的子树的 HASH 值排序,然后就可以非常好维护了。

  感觉和我之前学的树 HASH,有几个优点:

  • 被卡的概率转化为了字符串 HASH 被卡的概率,比较可靠,风险可控。
  • 方便记忆,不要再搞一些奇怪的函数。
  • 方便换根 DP。

  同时,对于无根树,可以找到重心,然后 HASH(如果有两个重心,那么可以取最小值)。

  对于这个题,如果没有度数限制,也可以通过换根 DP,做到 \(\mathcal O(n \log n)\)。

  然后就会发现 WA on test 11 ,然后楞了半天,拍了一堆数据,然后发现是因为树的形态比较多,于是 HASH 冲突了,转成双 HASH 即可。

  另,关于 HASH 冲突也找到了一些资料,可以日后分析时阅读。

  代码

这篇关于CF718D Andrew and Chemistry的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!