新建网站外链怎么做,商标注册的原则,怎么生成网页,wordpress 主题 美化版所谓启发式合并#xff0c;就是一种符合直觉的合并方法#xff1a;将小的子树合并在大的子树上。 这些问题一般是相似的问题背景#xff1a;都是树上的计数问题#xff0c;都不能直接从上往下进行暴力#xff0c;都需要从下往上计数时对子树信息进行运算从而得到父亲节点的…所谓启发式合并就是一种符合直觉的合并方法将小的子树合并在大的子树上。 这些问题一般是相似的问题背景都是树上的计数问题都不能直接从上往下进行暴力都需要从下往上计数时对子树信息进行运算从而得到父亲节点的信息。这个运算一般是启发式合并。
一般使用map保存子树的一些信息例如树的颜色树孩子的多少等等。选择map的原因我认为有以下几点
map可以非常方便地保存离散的信息而且可以对这些离散的信息进行遍历。这样的性质可以让我们方便地将孩子节点进行合并map可以方便地获得大小从而决定如何启发式合并map可以直接当作桶而不必要开那么大的数组
当读入信息树的边节点性质等以后我们用递归Dfs函数从根节点访问这个树
我们对根节点进行初始化把根节点当作一个树
然后递归访问节点的每个孩子
如果一个节点有多个孩子就要进行合并这个时候已经处理好孩子节点了来快速得到父亲节点的信息。
合并时我们一般要把小的树合并到大的上面。一开始的根节点也是一棵树我们已经进行了初始化因此只需要不断将根节点和孩子节点合并最后得到的树就保存了子树的信息。因为在合并的过程中可能会造成信息的丢失因为子树的重孩子不一定是树的重孩子所以我们需要一个数组保存答案。这样就不用担心数据丢失的问题。也不用害怕修改了子节点的值会造成影响因为是递归调用的当访问到该节点时其子节点的值都已经保存可以随便折腾。
重点就在合并过程(Merge函数)合并时我们一般遍历较小的map然后根据题目的条件进行合并。
最后得到答案。虽然挺有套路但是如何将问题转化成可以处理的形式是问题的关键。
