模拟赛4+abcfg(0.5+1)
T2 在链上跳+概率，可以转化为，一个一个判定选不选，这样来优化复杂度
T3告诉我们，能离线点分治，就不要点分树，不要相信stl/pbds的常数，再想出一个使用高级算法的做法后，一定考虑能否使用更简单的算法，如，给出在线做法后，应思考能否离线
T4神秘题目，有的时候，可以先忽略复杂度(计数题)，推出式子后，用类似插值的东西优化
这个题告诉我们，如果某一维特别大，可以考虑一些影响这一维的量，然后尝试用这些量表示那一维，然后再推公式，或者感觉很像插值的
令\(dp_{n,k}\)表示n个点的图，然后k次还不连通
推一波式子(这里是枚举1所在连通块)
\(dp_{n,k}=\sum_{i=1,n-1}\binom {n-1} {i-1}(\frac {i^2+(n-i)^2} {n^2})^k+\sum_{i=1,n-1}\binom {n-1} {i-1}\sum_{j=0,k}dp_{i,j}\binom k j(\frac {i^2} {n^2})(\frac {(n-i)^2} {n^2})\)
式子实在太依托了，不写了
然后考虑，图似乎和边数有关，所以考虑用\(f_{i,j}\)i是1-n,j是0-n^2-1表示dp然后递推f
然后地推有个重点是，f咋递推，发现k很烦，所以要把k里面搞的一样，所以(i,j)->(i+k,j+k^2)