数据结构

线段树求直径可以求任意子树（包括连子树都不算的分散节点集合）的直径，适用范围广。 线段树的每个节点所对应的区间$[L, R]$，指代了$Dfn$在$[L, R]$内节点，其中线段树上每个节点存储了$diam$（当前区间直径）及$lp, rp$（当前直径对应的左右端点），每次$Merge$操作分为全左区间、全右区间和横跨两个区间作讨论，对于第三种情况，选择两侧原直径端点求$Dist$取最值即可，正确性显然，查询直接通过$Dfn$查询即可。 当然可能有一些区间内的点不连通，先当作它们连通即可。 对于删除某些子树，相当于把整棵树分为$n$部分，查询每个部分，全部$Merge$起来即可。 例题Snow的追寻 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101 ...

前置「Hall定理」 二分图G中的两部分顶点组成的集合分别为X, Y(假设有|X|≤|Y||X|≤|Y|)。G中有一组无公共点的边，一端恰好为组成X的点(也就是存在完美匹配)的充分必要条件是：X中的任意k个点至少与Y中的k个点相邻，即对于X中的一个点集W ，令N(W)为W的所有邻居， 霍尔定理即对于任意W，|W|≤|N(W) 题解由于最坏情况任选 $k$ 个是选一端连续的区间 $[l, r]$，根据Hall定理的 $|W| \le N(W)$ 可以得到$$\begin{aligned}sum[l, r] &\le (r - l + 1 + d) \cdot k \\sum[l, r] - (r - l +1) \cdot k &\le d \cdot k\end{aligned}$$那么就可以在线段树中将每个点的权值设为 $value - k$，然后维护最大子段和 $sumax$ 那么最后 $sumax \le d \cdot k ? TAK : NIE$ 即可 代码1234567891011121314151617181920212223242526272 ...