【字符串】P4895

WeLikeStudying · 2021-12-20 20:23:20 · 题解

• 题目说得一点都不清楚（可能是因为它是从某 \text{OJ} 搞过来的吧，那为啥不把那充满文采的题目背景也搬过来呢）。
• 作者结合原 \text{OJ} 的文案再次对题面进行了改造。

题意是啥

• 原题链接。
• 给定一棵 n 个节点的无根树，对该树的节点进行黑白染色，要求任意两个黑点没有直接的边相连，求本质不同的染色方案模 10^9+7 的余数。
• 如果两个染色方案所形成的树可以对节点重新标号后，使得对于任意编号为 u 的节点，它在两棵树中只会同时为黑色或同时为白色，而且任意边 (u,v) 在两棵树中只会同时存在或同时不存在，则称两个染色方案相同（说白了两个方案的树同构）。
• 作者一开始根本不明白题目在讲什么，而唯一的题解……额，总之作者将围绕自己遇到的问题开始讲解。

最开始的思路怎么来的

• 看起来很像树论的树形计数动态规划对吧，但是树是无根的。
• 我们如果直接强行选定一个根的话，就可能出现这样一种情况：比如选定 u 为根，可能存在节点 v 满足 u\ne v 使得以 u 为根的有根树和以 v 为根的有根树同构，那样方案明显会算重复。
• 尽管我们还未确定具体的策略，但强后效性是不允许的。
• 有没有好的办法来避免这一问题呢。
• 我们知道，一棵树的重心与这棵树的根是哪个没有关系，我们可以尝试以重心为根。
• 那么重心为啥不可替代呢：因为如果有 u,v，u 是重心，以 u,v 为根的树同构，那它们最大子树相等，那么 v 也是重心，所以不用担心算重复。
• 请保证理解这些知识：一棵树最多有两个重心，如果有两个重心，那么这两个重心一定直接连边。
• 接下来我们重点讲解只有一个重心的情况，最后再解析如何求解有两个重心的问题。

如何计算方案数

• 我们已经在实质上将无根树转化为有根树进行求解了，接下来问题就在于计算方案数。
• 首先可以很套路地设出 f(u,0/1) 表示以 u 为根（u 是否染成黑色）的子树的染色方案数，转移比较基本。
• 接下来遇到一个很严重的问题：u 可能有很多个不同的子树，这些子树如果两两不同构那当然好处理，但如果有同构的怎么办？（先忽略我们还不知道树同构如何判断的事实）
• 打个比方，我知道有 m 棵同构的树，它们的方案数都是 n，那么它们对 u 的贡献是多少。
• 转化为一个简单的问题：n 个物品中取 m 个（可以取重复）的总方案数是多少？考虑在 m 个物品中间插入 m-1 个防止取走重复，总方案数为 C(n+m-1,m)。
• 接下来作者将解析如何判断树是否同构。

哈希判断树同构

• 作者知道有很多判断树同构的哈希方法，但作者介绍的方法有这样的特点：哈希只是一个辅助手段，如果没有哈希方法，对于一棵节点数为 n 的有根树，构造它的复杂度是 O(\frac{n^2\lg n}{\omega}) 级别的，但最后会得到一个 100\% 正确的判断树同构的编码。
• 理由很简单：作者希望自己的哈希通过随便更改模数的方法就可以避免针对，而不是寄希望于数据多水。
• 作者的哈希值以 01 串的形式编码。
• 方法很简单：叶节点的哈希值为 H(u)=01。
• 对于节点 u，节点按照哈希值字典序大小排序（由于要求本质相同所以要排序），编码为 v_1,v_2,\cdots v_m，那么有： H(u)=0H(v_1)H(v_2)\cdots H(v_m)1
• 可以轻易地将其当作二进制整数进行编码，下面是一个例子：
• 通过这样的方式，即可用 O(n\lg n) 的时间，算出树上每个节点的哈希值，并以哈希值的相等与否来比较子树的同构与否。
• 编码时可以同时计算子树大小和答案，起到辅助哈希的效果。

有两个重心的情况

• 有两个重心怎么办？
• 如果有两个重心，那么这两个重心一定直接连边。
• 断开这条边，变成两个子树（显然相当于有根），分情况讨论就好了：
• 分析如果两棵子树同构应该怎么办，如果不同构应该怎么办，已经不是最困难的部分了。

代码实现

• 代码实现。
• 作者是 1A 的，思路稳当，打得自然顺畅。
• 这里作者记一下代码细节，如果您实现出现问题的话也可以看看。
• 一定要在深度优先搜索之后记录搜索的节点，不然会被覆盖。
• 记录的节点要套一个数组，不要直接写下标。