力扣2003三种解法 启发式合并、线段树维护mex运算、思维
题目链接
给出一颗有根树,每个节点有一个权值$w_i$,求出所有子树的mex值,一个子树的mex值定义为在该子树中最小的未出现的正整数。
题解
Solution I
启发式合并
考虑暴力维护每颗子树包含的数据,当前子树包含的正整数就是所有儿子包含的正整数加上根,并且根据mex运算性质,父亲结点的mex值肯定大于等于儿子结点。
但是暴力合并的时空复杂度都是$O(n^2)$。可以在合并的时候每次都将小的集合往大的集合合并,这样时间复杂度最坏为$O(nlogn)$。(当树为满二叉树的时候)
代码:
1 | class Solution |
Solution II
可以发现,权值为1到根结点这一条链上的答案不为一,其他点的答案都为1。因此可以考虑拿出这一条链暴力维护。有上面mex的性质,时间复杂度为$O(n)$。
代码:
1 | class Solution |
Solution III
根据dfs序重新标号。用线段树维护区间mex。代码有空再补。