n个点的树m次询问,每次对(x,y)路径上的点发放颜色z,输出操作结束后每个点拥有的数量最多的颜色。n,m,z\leq 10^5

Solution 1.

一种相对简单的想法是对每个点暴力开桶,统计答案,这样的话空间和时间都是O(n^2)的,无法承受(即便是有其他数据结构也不能改变\sum_u \sum_i [i\in c_u]O(n^2)量级的事实)。也就是需要考虑让每次操作影响到的点变成O(1)个。

我们注意到一个点u被路径(x,y)覆盖当且仅当y,x其中至少一点在以u为根的子树中(对于两个都在u的子树中且u被覆盖的情况当且仅当u={\rm LCA}(x,y)),显然这个时候对路径(x,y)的端点x,y挂颜色后他们\rm LCA以下的所有祖先都会受到影响,显然树上差分即可,这个时候颜色的总量是O(m)的,转化成了询问每个点子树中数量最多的颜色个数,dsu或者线段树合并即可,复杂度O(n\log n)

或者说很容易联想到树上前后缀的链覆盖和\rm LCA覆盖之类的事情

Solution 2.

像 Solution 1. 中提到的,维护一个桶和他的最大值容易联想到线段树,上树后为树链剖分,落成把链(x,y)操作拆分成O(\log)个区间操作,差分之后落到对应的点上,然后暴力扫一遍,同时权值线段树维护。一共O(m\log n)个操作,单次维护O(\log n),总复杂度O(m\log^2 n)

Solution 3.

考虑对每个颜色分别处理,建出虚树以后O(n)-O(1)处理一下\rm LCA,原树上的每一条链都被抽象成了一个边,然后覆盖次数就是边权,若干次操作以后对一条链取\rm max,对树上边权排序,之后用并查集维护操作过的点,同时对没被操作过的点重标记设\max 。为了继续保持优秀复杂度,分块之后四毛子,最后可以强行做到O(n)

重链剖分 树上问题 虚树 树上启发式合并 并查集 四毛子

2022.9.19补
上一篇 «
2022.8.25补
» 下一篇
© 2017 - 2024 云雀.
...... visits · ...... visitors