NAIPC 2017补题

D

给定一棵$n(n\le 2e5)$个点的有根树，每个点有点权，选出一些点，使得这些点的满足大根堆
的性质，求最多可以选多少点。

如果是一条链，就是求LIS，做法是维护一个单调队列。
树的话，其实也可以用单调队列，不过需要对不同儿子节点的队列进行合并。
可以考虑用multiset，进行启发式合并。

E

有$n(n\le 2e5)$个点，其中$s$个是特殊点。有$m(m\le 5e5)$条候选边。需要求一棵最小生成树，使得恰好有$w$条边是普通点和特殊点之间的。

其实就是边有两类，每一类选的边数固定，求最小生成树。
如果直接Kruskal，遇到一类边选满后跳过的话，是有问题的。
考虑带权二分，即把其中一类边统一加上一个权值，然后跑Kruskal，直到每一类选的边数恰好符合要求。
不需要每次都把边混在一起排序，可以用two-pointers。

G

有一个$n\times m(n,m\le 50)$的矩阵，每个格子里有一定量的苹果（每个苹果1元）。有$k(k\le 1e5)$个顾客，每个顾客带了一定数量的钱，且只能在一个子矩阵内购买苹果。求最大总消费量。

网络流，但直接建图边数是$O(nmk)$的，会MLE。
可以考虑二维线段树优化建图，把边数减少到$O(nm+k\log nm)$。

H

有一个$n$个点的完全图，每条边有一个颜色。该图满足：任意一个简单环上必定存在一对相邻边同色。
定义$f(S)$为点集$S$中最大同色（即图中所有点间的边颜色相同）子图的大小。
求${\sum }_{S\subseteq [1,n]}f(S)$。

可以证明图中必定有一个点的所有出边颜色相同。
去掉这个点后剩下的图依然满足。
因此可以转化成一个长为$n$的序列。
然后搞dp