随机原因下又能来三轮了，那我二轮最后不白 recall 了（）
\(\text{day0}\)
前一天又失眠了，早上起来直接收拾东西赶高铁，下午四点多到了青岛，哎打车怎么要了四十块钱，黑心司机啊。
看到地图上显示到 cyyz 只有 \(2.2\) 公里，徒步走了一会，发现显然不止 \(2.2\) 公里，过了半个多小时才到，签了到之后上楼配了下电脑坐公交回酒店吃外卖。
试机赛怎么典完了，T1 怎么 \(n\le 11,\bmod 10^9+7\)，这我哪会啊，T2 送了 \(65\)，然后咋办，\(O(nm\sqrt {nm}\log nm)\) 有机会过 \(nm \le 3\times 10^5\) 吗，没什么前途啊，这我哪会啊，T3 怎么是解解概率方程，这我哪会啊。
T1 还真是哈集幂，怎么过了一万个人，T2 怎么是按照 \(2\times 2\) 正方形刻画，哦好有道理，这题好玩唉，T3 忘了。
半夜又失眠了。
\(\text{day1}\)
没睡醒。
这 T1 是啥，暴力给了 \(50\) 吗，T2 \(n^2\) 怎么才 \(20\) 分，哎是不是根号分治一下就单根号或者挂个 \(\log\) 了，这真能跑过 \(10^5\) 吗，我靠怎么才 \(35\)，T3 怎么是网络流，这我哪会啊。
奥奥 T1 稍微拆一下卡一卡常暴力就 \(70\) 了，然后呢，不会啊。T2 更没前途了吧，我靠 T1 怎么过了一车，开始嗯推。
嗯推了一两个小时，感觉暴力拉插就大概是对的，写了一个多小时调出来了，哎怎么还是 \(70\)，哎怎么 \(T=1000\) 跑了 65s？？哦好像是 \(O(T\log^4 n)\) 的，死完了啊，不是我 T2 还没写呢。
趁早退役吧。
T1
拉插好像没什么前途，研究了半天也没什么优化的好办法。
考虑组合意义，\(g(n) = g(n-1) + g(\lfloor \frac{n}{2}\rfloor)\) 等价于 \(2n\) 的 \(2\) 整数次幂的拆分数，考虑对于 \(2^j\)，其有 \(j+1\) 种本质不同的拆法，其他的都可以进一步转化由其他的数到。
然后设 \(f_{i,j}\) 表示用 \(2^x(x \ge i)\) 拼出 \(j\times 2^i\) 的方案，套个组合数转移就行了，复杂度 \(O(T\log^3 n)\)。
组合意义牛完了，gemini 有点牛的。
\(\text{Submission}\)
T2
好题，链接挂的是弱化版。
考虑维护一个二元组，当前拼了多少链和剩余长度，暴力容易做到 \(O(n^2)\)，然后根号分治一下，对小的暴力，大的发现只有 \(O(\sqrt n)\) 个本质不同的答案，二分找区间即可，复杂度平衡一下可以得到 \(O(n\sqrt{n\log n})\)。
\(\text{Submission}\)
然后我们需要把根号扔掉，考虑类似长剖，每次继承重儿子的信息，然后暴力合并轻儿子，但是这里需要具体讨论一下：
记 \(K\) 为所有轻儿子的最大 \(siz\)，\(d_i\) 为 \(i\) 到叶子的最长链，\(f_{i,l}\) 表示 \(i\) 点拼了 \(f_{i,l}\) 条长度不小于 \(l\) 的链，\(g_{i,l}\) 表示 \(f_{i,l}\) 条件下最大的剩余链长。
对于 \(l > K\)，显然此时 \(f_{i,l} = 0,g_{i,l} = d_i\)，因为子树内的最长链长度不超过子树大小。
进一步，根据 dsu on tree 的结论，所有轻儿子子树大小和为 \(O(n\log n)\)，本题中，所有点的答案和为 \(\sum \frac{n}{i} = O(n\ln n)\)，因此我们只要暴力对 \(l \le K\) 的部分合并，对 \(l > K\) 的部分暴力更新每个点答案。
写一点实现细节，我们可以对每一条重链开线段树，其大小为 \(siz_{top}\)，避免了线段树合并。先用每个 \(d_i\) 更新对应的 \(g_{i,l}\)，然后将每个轻儿子所在链的线段树信息暴力取出来更新 \(g_{i,l}\)，顺带删掉就行了。
最后找到 \(l > K\) 的部分，用轻儿子最大距离 \(D\) 和每个区间判断是否存在合法链，存在的话继续递归直到叶子暴力修改，否则区间加一区间取 \(\max\) 就行了，注意叶子节点有一些细节。
复杂度 \(O(n\log^2 n)\)，细节挺多的。
\(\text{Submission}\)
T3
原始对偶，互补松弛定理，一个都不会喵。