1.5 KiB
1.5 KiB
一、朴素思想
要想求出每个点存放最多的是哪种类型的物品，需要求出每个点上存放的每种物品的数量。
朴素做法，对物品的类型进行离散化(最多 M 种不同物品)，然后对每个点 x 建立一个计数数组 $c[x][1$~$M]$。
依次执行每个发放操作，对 x 到 y 的路径上的每个点 $p$， c[p][z]++ ，最终扫描计数数组得到答案。
因为路径上每个点都需要执行一次$++$操作，但是这样肯定超时，因此需要优化。
二、树上差分优化
为了避免遍历从 x 到 y 的路径，我们可以使用树上差分，对于每条从 x 到 y 的路径上发放 $z$，使 $c[x][z] + 1$，使 $c[y][z] + 1$，由于路径上所有点都 $+ 1$，包括 x 和 $y$的最近公共祖先，因此需要使 $c[lca(x, y)][z] - 1$，使 $c[father(lca(x, y))][z] - 1$。
三、线段树+线段树合并优化
为了节省空间并快速使两个计数数组相加，可以使用线段树合并:
- 对于每个点建立一个动态开点的线段树，来 代替差分数组，动态的维护最大值以及最大值对应的类型，然后深搜求子树和，每次的求和等价于每两个线段树合并，最终得出每个点的答案。
四、关于离散化
看题解有的网友说$z$的范围是1e9,需要开离散化，所以代码中都有离散化的部分。
但看了下，无论是洛谷还是AcWing,现在的数据上限都是1e5,开不开离散化都行。