LCT

A. Cave 洞穴勘测

　　LCT模板题，只需要维护一棵树的联通性即可。

B. tree

　　好像是为数不多LCT实现区间修改的题？注意打标记，先下放乘法，再下放加法，乘法顺便在加法标记上乘一下就完了。

C. 水管局长数据加强版

　　如果没有报废操作，那么只要用最小生成树维护链上最值即可。

　　然而水管的报废很难找到一条能够替代它的另一条边，那么考虑时光倒流，将删边操作转化为加边，只要链上对应的最大值>当前边，那么将这条边替换一定不会变劣，LCT维护即可。

D. GERALD07加强版

　　由于强制在线，所以回滚莫队之类的骚操作就没了。

　　森林的联通块数非常好求，所以只要保证这些边形成的图是无环的，那么就可以解决这个问题了。

　　可以发现，若一些边形成了环，那么编号最靠前的边一定是最先没有用的，可以考虑给每条记录一个pre，表示它加入会使哪条边费掉，查询时只要查询这个区间内pre不再这个区间的即可。

E. Sone1

　　咕

F. 大森林

　　思路非常好的一道题。

　　可以发现，如果将0操作的区间扩展到$[1,n]$，那么对于询问的答案不会有任何影响。

　　可以发现，如果将所有询问放在最后处理，对于询问的答案也不会有任何影响。

　　这其实就启发了我们离线的思路。

　　对于每个1操作，新建一个虚点，最初连在上一个虚点上，等到到达要求的区间时，再将这个虚点连到需要换到的位置。

　　然后每次考虑相邻两棵树的差异，依次处理即可。

　　需要注意的是，这道题不能用split求树上两点的距离，因为树上有虚点，两点之间的在原树中链上的点可能并不在LCT中的链上，那个位置可能被一个虚点取代，而虚点连着这个实点，因此只能用LCA求树上两点间的距离，找到$deep[x],deep[y],deep[LCA]$即可，至于换根操作是可以允许的，但是求距离的时候必须保证根为1（其实就是不能换根）。

G. 在美妙的数学王国中畅游

　　其实这道题里LCT只用到了模板。。。主要是导数方面的知识。

　　$f(x)=e^{ax+b}$    $f^{(i)}(x)=a^{i}e^{ax+b}$

　　$f(x)=sin(ax+b)$   $f^{(1)}(x)=acos(ax+b)$

　　　　　　　　　　 $f^{(2)}(x)=-a^{2}sin(ax+b)$

　　　　　　　　　　 $f^{(3)}(x)=-a^{3}cos(ax+b)$

　　　　　　　　　　 $f^{(4)}(x)=a^{4}sin(ax+b)$

　　然后用泰勒展开成多项式，LCT维护链上的系数和即可。

H. LCA

　　首先将深度差分，那么一个点所能造成的贡献就是祖先链上点的个数。

　　那么对于某个询问的点来说，祖先链上的某个点所能够造成的贡献就是这个点子树中包含询问区间点的个数。

　　使用LCT实现链上加即可。虽然我打的树剖

I. 即时战略

　　神奇的一道题。。。对LCT理解不够深刻。。

　　先考虑链，看数据范围要求是$O(n+log)$。

　　维护当前探索到的链的头和尾，考虑从头走向还没走过的一个点，如果走到了一个新的点那么一直探索下去，否则从尾向这个点走去，一直走到。这个过程的期望是$O(n+log)$

　　对于其它情况，考虑使用LCT来完成探索某个点的过程。首先走到某个点，然后探索，如果这个新的点与这个点在同一棵$splay$中，那么在$splay$上根据这个点所在哪棵子树就可以实现二分，如果不在同一棵，那么直接找到那个点对应的splay，继续完成二分的过程，直到探索到一个没有到达过的点。

　　然而有一些奇怪的地方，并不知道为什么。比如为什么找到一个没有到达的点时立刻assess会使操作次数增加？