CVBB ACM Team

• 分类：树形$DP$ ，根号分治

• 题意：给定一片森林，$q$ 此询问，每次给出两个点 $u,v$ ，如果 $u,v$ 在一棵树内输出 $-1$ ，否则在这两棵树任取一点临时建立一条边，求连边后的直径的期望。$n,q\le 10^5$

• 题解：首先我们可以预处理出每个点在哪棵树中，其次预处理出每个点 $u$ 到这棵树叶子的最大值 $mx[u]$ ，这个可以用树形$DP$ 处理，将每棵树按照这个最大值进行排序，最后在处理出每棵树的直径长度 $len$ 。询问的时候枚举点数少的树，在另一棵树中寻找另一个点。将两棵树连接 $u,v$ 后的直径有两种情况：$mx[u]+mx[v]+1$ 和 $\max(len[u],len[v])$。第二种情况是一个定值，因此对于每一个 $v$ 我们可以二分出满足第一种情况的 $u$ 的个数，剩余的即为第二种情况。最后答案要用$map$ 记录下来避免重复询问。复杂度是神奇的 $O(n\sqrt{n}\log{n})$

• comment：根号分治太神奇了

• 分类：$dp$

• 题意：给定$n$个带有权值的第一象限的矩形，并且每个矩形有两条边与坐标轴重合，选择一个子集，使得子集内的矩形面积并减去权值和的差最大

• 题解：按照横坐标排序后，可以写出一个$dp$转移式，$dp_i=x_i*y_i-a_i+\max (-x_j*y_i+dp_j)$，而$max$后面的式子可以通过凸包来维护，为了熟悉板子的使用换了插入直线和查询单点最大值的做法，需要注意由于可能存在负数，需要插入$(0,0)$

• comment：$dp$的转移式的推导比较巧妙，之后就变成裸题了，（为什么会放在$1E$啊草）

• 分类：

• 题意：

• 题解：

• comment：

• 每日亿题2020.8.2
• 每日亿题2020.8.7

• 摸了

• 每日亿题

意外情况，摸了