python/TangDou/AcWing/P4556.md

### 一、朴素思想
要想求出每个点存放最多的是哪种类型的物品，需要求出每个点上存放的每种物品的数量。

朴素做法，对物品的类型进行**离散化**(最多 $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$,开不开离散化都行。