H

ZRC&LYF 签到

E

题意：

n1e5。以1为根的树上，越深的节点点权越小。q1e5个询问，询问节点x在[l,r]权值区间内的连通节点有几个。（说得不太清楚，就像是能传染点权在[l,r]间的点，问能传染几个点）

第一步通解：

显然应该先跳到点权<=r的最上方祖先。

WD解：

考虑在每个节点得到答案所需的信息都是子树的值域情况。离线dsu on tree可以解决。

另解：

维护子树信息类问题都可以利用dfs序将树摊成数列再考虑。那么问题就转化成了，求区间权值大于等于l的有多少个。显然是主席树可做问题。

J

题意：

题目比较绕，内核就是一张这样的图，每个点有一个点权。每秒钟可以选择一条边，使得它连接的两个点点权均-1。问将所有点的点权都减到0的最短时间。

解：

比赛时的想法首先是带花树。将每个点拆成点权个点，跑一般图匹配。但是如果卡这种做法的话显然是过不了的。（但是出题人没卡）

WD发现这个问题显然可以用单纯形做，AC

题解：

枚举其中两条边的流量跑二分图匹配。

启发：

由某经典题库（虽然有点烂）《线性规划与网络流24题》可见，线性规划常常与网络流出现在一起。相似的例子还有【NOI 2008】志愿者招募，既可以用单纯形，也可以转化成费用流问题。事实上，所有网络流问题均是线性规划问题。当数据范围较小时，单纯形法完全可以成为网络流相关算法的备用方案，免去了对建模能力的要求。

同时，枚举两条边的流量使其变成经典问题的操作也是应当掌握的。

补题

待补

由于是本校出题，最好都看一看