bzoj 4754: [Jsoi2016]独特的树叶 树哈希

题目链接:https://www.lydsy.com/JudgeOnline/problem.php?id=4754


我们只需要找到一种方法,可以快速的判断树B删掉一个叶子之后是否与树A同构

最快的方法肯定是判断:以叶子节点的父亲为根时的hash值是否在A中存在

所以我们先求出每个点的子树的hash值,然后再进行换根,记一下前后缀的哈希值就行了

求出A树每个点为根的哈希值后,放进map里记录一下,如果B树删掉了某个叶子之后的值在map中出现了,那么就是我们要找的点

%Sinogi大佬

详细的讲解我会另写一篇博客

 

bzoj 4754: [Jsoi2016]独特的树叶 树哈希》有1个想法

发表评论

电子邮件地址不会被公开。 必填项已用*标注