问题是要求 ，考虑二分答案后，使用二分图匹配判断是否流满。

但是，我们不能暴力的去建出二分图，对建图进行优化。

首先，我们考虑对每种颜色建出虚树，那么一条边就对应原树的一条垂直树链，这条链上任取一个点都会产生颜色树乘子树关键点数的值，因此需要将这条路径的所有点连向某个值。

然后，这里给一个 个点， 条边的建图方式。第一部分，考虑对树轻重链剖分，每个点拆分为本来的点，连向它在重链上的副本，并将这个点连向重儿子在重链上对应的点，第二部分，对剖分后的 dfs 序使用线段树优化建图。因此，每条垂直树链就可以分为一系列重链（到链顶端），加上一段 dfs 序连续区间。

第一部分的建图，如下所示。可以注意到，若一个点往外有流量时，这个点所属重链的所有祖先结点也可以通过这条流量。

image.png

因为，一条垂直树链至多有 条重链，因此这部分至多会创建 条边，而线段树一次区间询问至多由 个区间组成，因此总边数为 的。

将图建出来后，二分答案时，不需要每次重新跑一边最大流，如果 成立，那么可以继续在它的残量网络上继续跑，否则撤销本次操作。