T1
我是个大聪明！一眼矩乘。构造转移矩阵构造了3.5h！最开始以为只有 \(15\times15\)，直接手打。写到一半发现不一定四种颜色都有，是 \(52\times52\) 的，这时候狗被脑子吃了，还想手打，于是就打到了3h。差不多打了一大半，脑子终于把狗还回来了，意识到就算打完也不可能调得出来，就开始另辟蹊径，终于在又过了0.5h用最小表示法构造出了转移矩阵，A掉了。但是后面的暴力就根本没有时间打。
将问题转化成 \(4\times n\) 网格图上点横竖连通。dp 状态共 \(52\) 种，矩阵快速幂优化 dp 解决。
T2
暴力没打出来。
考虑将分开时的深度和 \(ans1\) 和合起来后增加的深度和 \(ans2\) 分开维护。
分开时的深度最开始整体求一遍 \(O(n)\)，每次rotate \(ans1\) 都只需对两个 \(size\) 加或者减。
关于 \(ans2\) 的求法，有一个小技巧就是 \(\sum depth=\sum size\)。合并时经过的点都是左树右链和右树左链上的。如果当前点是左树上的，那么 \(ans2\) 就会加上右树剩下的 \(size\) 反之亦然。那么就相当于是两个指针在两条单调下降序列上跳，权值线段树维护即可。rotate 操作最多修改左链或右链上常数个点。
T3
考后看了一下，如果T1不犯浑，这题还是可以自己推出来的。
就一个简单的 dp，完。
设 \(dp_n\) 表示 \(1-n\) 的每个排列构成的笛卡尔树的答案，\(f_n\) 表示 \(1-n\) 的每个排列构成的笛卡尔树按题中走法期望走到的点数。很容易得到转移方程：
\[\begin{aligned} f_n=&\frac12\sum_{p=1}^{n}\binom{n-1}{p-1}(f_{p-1}\times(n-p)!+f_{n-p}\times(p-1)!)+n!\\ \frac{f_n}{n!}=&\frac1n\sum_{p=0}^{n-1}\frac{f_p}{p!}+1\\ dp_n=&\frac12\sum_{p=1}^{n}\binom{n-1}{p-1}[(dp_{p-1}+f_{p-1})\times(n-p)!+(dp_{n-p}+f_{n-p})\times(p-1)!]+n!\\ dp_n=&\sum_{p=1}^n(dp_{p-1}+f_{p-1})\times\frac{(n-1)!}{(p-1)!}+n!\\ \frac{dp_n}{n!}=&\frac1n\sum_{p=0}^{n-1}\frac{dp_p}{p!}+\frac1n\sum_{p=0}^{n-1}\frac{f_p}{p!}+1\\ \end{aligned} \] 标签：20230706,frac,sum,暑期,times,ans2,集训,dp,size From： https://www.cnblogs.com/dks-and-xiao-yu/p/17536051.html