首先第一次卡的点在到根路径能否拆到每条边上，因为我忘记了期望的可加性是否要满足各个部分独立了，后面手推了一下，发现没问题。然后问题就转成了问每条边是重边的概率，考虑设状态 F_{u,i} 表示在 u 的子树里面，重链长度为 i 的概率，这个东西的转移是 F_{u,i}=\sum_v F_{v,i-1}\sum_k \frac{i-1}{i-1+k}G_{v,k}，其中 G_{v,k}代表 v 的兄弟重链长度和为 k 的概率。我一开始误以为直接求 F 是 O(n^3)，而求 G 是 O(n^2) 的（后面发现两个反了），然后就糟糕了，我一直在想 F 这个式子怎么优化，想了好久，决定破罐子破摔打 n^3 了，然后打到一半，发现求 G 也是 n^3，而且更难优化，然后我就只能硬着头皮打下去了。不知道为啥这东西这么难调，调了好久，打完的时候已经没时间了。发现自己最后的一个大样例跑了0.6s，因为加了很多卡常剪枝，不知道能拿多少。
T2
赛时没时间了，打了个状压就跑了。
Day 2
T1
交互题，一开始从 p_0=0 开始突破，发现这个情况就是一直往右扩展就行了，当前缀 \mathrm{mex} 变化时，说明这个值是可以确定的，然后中间跳过的值随便填就行了。然后我首先发现了单谷的 n+\log n 做法，就是找到 0，然后将已知数的区间向两边扩展，哪边能扩就扩哪边，其实可以省掉找 0，直接从大到小缩区间也是可行的就变成 n 的了。综合这两个部分分，我就想到了 2n+\log n 的做法，加了记忆化就能变成 1.5n，也是先找到0，然后像第2种情况一样先看左边还是右边能扩展，然后像第1种情况一步一步扩展就行了。但是这种做法每一步要多一次找方向，于是我就一直在想如何减少这一步，结果还是没搞出来。然后我开始分析数列的性质，注意到有值的序列一定是单谷的，但是我当时没想到办法来求出这个单谷的序列，所以到最后还是没想出来。实际上，如果反应到了 \mathrm{mex} 等于补集的 \min 这个性质的话，这题就很好做了。首先跑出前缀 \min，找到 0，然后从 0 开始找后缀 \min，这个序列就找出来了，填其他数也是一样。考试的时候，我还是太高估这题的难度了，没办法，有点被样例误导了。