Day1:
起床困难综合症：按二进制位从高位到低位贪心，能得到１则选１。
魔法森林：
Link-Cut-Tree动态维护最小生成树（最小瓶颈生成树）。
按边按a[i]从小到大排序，按顺序插入，维护以b[i]为边权的最小生成树，可以证明最小瓶颈即最小生成树上经过的最大边。
支持link,cut,query_max，Link-Cut-Tree即可。
Day2:
动物园:求出fail数组之后连边(fail[i],i)，形成一个树形结构。i节点的num[i]即为它在树上到跟的路径经过的<=i/2的节点数。stack+二分即可。
随机数生成器：贪心。能选小的就选小的，维护当前可放位置，因为每个位置只会被标记为不可放一次，所以复杂度是靠谱的。
购票：很裸的斜率优化。但是因为加上了转移范围限制所以要用线段树维护区间的凸壳。又因为在树上所以我就数链剖分了。复杂度较高，推荐另外一种树分治的写法。
原文：http://www.cnblogs.com/iamCYY/p/5013830.html