Day 0

笔记本在出发之前很惨烈挂了，于是这次的高铁上咱修了一路电脑。结果最后似乎还是没有要好起来的迹象哭qwq所以这次集训咱大概是只能用机房电脑了……有种莫名的落魄感啊。
晚上和一同前来的各位进餐，熟悉机房环境（这来过了2次的机房我还需要熟悉吗？？），然后咱又可以坐在咱半年前的座位上了！感觉有种微妙的既视感呢

Day 1

听说是提高难度的题啊（而且好像又一次是为了我们准备了难度较低的题）不过做起来大概就是另一回事了

T1 梦境

线段树综合征犯了【趴
一眼就看到区间两个字，差点脑子一热就打线段树了。不过仔细一想好像没有什么可行的能维护每个区间的左右端点的方案，而且第一反应想出的贪心被很快找到了反例【趴 然后再读题，注意到一个区间只对应一个点的话……二分图匹配？从NOIP2018的经验来看的话T1不可能这么恶心啊……
于是便注意到了一个可行的贪心方案。我们每次用右端点距我们枚举到的某个点最近的那个区间来对应我们枚举到的这个点。至于正确性，我们可以注意到，一个点无论被哪一个区间对应都是等效的，那么我们希望我们每次取到的这个区间不会使得其他区间无法找到对应的点。我们每次找到右端点最近的这个区间，即使该区间可以对应其它的点，我们将这些点留给这个区间之后的其它的区间不会使得答案更差。
接下来，我们注意到我们需要维护在每一个点的位置上有多少区间还没有用以及右端点最近的是哪一个区间。这可以用扫描线+优先队列来实现。
咱做这题的时候忽略了一个问题：如果我们在扫描的时候遇到一个已经无法再被任何区间包含的点的时候，它不会跳过这个点，而是被这个点卡住不动。因此，在评测中得到了20分的好成绩qaq

T2 玩具

这个题我真的是差点就读懂了，Thumbs up!
说白了其实就是棵n个节点的多叉树，求其期望树高。那肯定是DP啊，但像我这种DP一问三不知的家伙怎么可能会写啊【趴
我们考虑这棵树去除树根后就是一个森林，那么我们可以考虑把n个节点的情况看作一个有n-1个节点的森林，其最后的树高就是这个森林里最高的树的树高加一。我们设g[i][j]为有i个节点的森林，其树高不超过j的概率，设f[i][j]为有i个节点的树，其树高不超过j的概率，那么显然f[i][j] = g[i-1][j-1]，即，我们在有i-1个节点的森林的最上方添加一个根节点，其概率保持不变。考虑如何转移。对于g[i][j]，可以认为是由一棵有k个节点的树和有i-k个节点的森林组成。然而我们需要考虑这k个节点在这棵树上的概率。
我们令dp[i][j]为一个有i个节点的森林，其中j个节点在一棵树上的概率。那么，dp[i][j] = dp[i-1][j-1] * \frac{j-1}{i} + dp[i-1][j] * \frac{i-j}{i}。我们可以预处理出这个dp数组。
那么，g[i][j]的转移方程为g[i][j] = \sum\limits^{n}_{k=1} f[k][j] * g[i-k][j] * dp[i][k]

T3 飘雪圣城

看到树就想树剖LCT我没救了（似乎确实有个LCT+莫队的做法，不过你觉得我会莫队嘛）
其实正解这个思路我想到了只是没有想到怎么做【趴 告诉你这个图是个树的目的就是得出每连一条树上边就一定减少一个连通块。那么我们同样也可以这么做。我们只要求出l \sim r中有多少条边即可。
于是这道题就变成了一个类似二维偏序的东西。我们给定l和r，求有多少条边满足l<=x且r>=y。于是我们就可以离线排序树状数组一套带走。
具体一点的话就是我们把边按x小y大存起来，按x排序，将所有y加入树状数组维护。然后枚举每一个询问，如果有x已经小于当前询问的l，那它再也不会产生贡献了，我们从树状数组里面把它删掉即可。

下午讲题的时候咱用的机房的电脑突然蓝屏然后就开不了机了……我是肉体EMP发生器么
于是换到了另一台之前用过的电脑上（之前下的Summer Pockets居然还在上面！不过SP咱已经推完了就是，有时间还是想写个长评啊），现在这篇博客就是在这台机子上打的！
今天差不多就这样了吧，今晚咱大概要睡早点了，今天一整天都没啥精神啊