You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
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,开不开离散化都行。