### 一、朴素思想 要想求出每个点存放最多的是哪种类型的物品,需要求出每个点上存放的每种物品的数量。 朴素做法,对物品的类型进行**离散化**(最多 $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$,开不开离散化都行。