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.
This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.
### 一、朴素思想
要想求出每个点存放最多的是哪种类型的物品,需要求出每个点上存放的每种物品的数量。
朴素做法,对物品的类型进行**离散化**(最多 $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$,开不开离散化都行。