题解 P4323 【[JSOI2016]独特的树叶】

2019-05-07 20:12:43


树 $\mathrm{hash}$ + 换根 $\mathrm{DP}$ 。

先考虑一个 $O(n^2)$ 的做法。

先求出以每个节点为根,整棵树的 $\mathrm{hash}$ 值。可以做 $n$ 遍 $\mathrm{dfs}$ 得到。

然后,把 $A$ 的所有 $n$ 个 $\mathrm{hash}$ 值丢到一个 $\mathrm{map}$ 里去,然后枚举 $B$ 的每一个叶子节点,判断删掉后的哈希值是否在 $\mathrm{map}$ 中即可。

这个算法的主要瓶颈在于 $O(n^2)$ 求 $\mathrm{hash}$ 值,我们考虑优化这个过程。

异或满足可减性,很容易抵消掉。所以我们设哈希函数 $f_i=\bigoplus\limits_{j\in Son_i}(f_j\times W+sz_j)$ 。

对于每棵树,我们设 $f_i$ 表示上面的哈希函数, $h_i$ 为以 $i$ 为根时整棵树的 $\mathrm{hash}$ 值。

这样就可以先一遍 $\mathrm{dfs}$ 求出 $f$ ,再一遍换根 $\mathrm{DP}$ 求出 $h$ 了。

具体的, $h_i=f_i\oplus\Big\{\big[h_{fa}\oplus(f_i\times W+sz_i)\big]\times W+(n-sz_i)\Big\}$ 。特殊的是当 $i$ 为根时 $h_i=f_i$ 。

这个式子不太好解释,建议自己画图理解。

那么这样子求 $\mathrm{hash}$ 值就降到了 $O(n)$ ,总时间复杂度为 $O(n\log n)$ 。

具体实现及细节见代码