1014总结
总结
时隔接近一个月写的考试总结...
T1
没有什么价值的题，分析一下相位这些就可以做出来。
T2
算区间最大值之和要枚举最大值位置算跨过的数量，所以考虑对这个东西动态规划，设 \(dp[l][r]\) 表示只考虑 \(l,r\) 区间的最优答案。
枚举最大值位置后，拆分成两个区间，其答案和最大值位置以及彼此无关，符合最优子结构性质，加上最大值的额外贡献，可以在每一个位置枚举取哪个值，有可能算出来答案比较劣，但是仍然可以遍历解空间，所以这样 DP 没有问题。
枚举取值的复杂度很高，发现每个位置的最优值和 dp 数组无关，考虑预处理每个位置的最优值，本质上是给定若干一次函数，再给定若干 \(x\)，求最值，很简单。
T3
考场上没有做出来的题，但是基本想出来了，ARC 那道期望题加深了对期望的理解。
根据期望线性性，\(E(dis_{u,v} ) = E(dis_u)+E(dis_v)-2\times E(dis_{lca(u,v)})\)。
前两者是好算的，考虑这样一个 \(dp\)，\(dp_u\) 表示 \(1\) 到 \(u\) 的期望距离，转移比较简单。
考虑后者怎么算，即 \(u,v\) 两点 \(lca\) 距离的期望，如果 \(v\) 在下面，由于 \(lca\) 一定在 \(u\) 及之前，所以 \(u,v\) 的 \(lca\) 的期望等价于 \(u,u+1\) 的 \(lca\) 的期望，归纳即可证明。
考虑计算 \(u,u+1\) 的 \(lca\) 的期望值，这个也是可以动态规划的了，枚举 \(u+1\) 的祖先即可，上前缀和优化。
T4
我的想法
考虑类似点分治一样去做，只不过是随机选点，期望层数应该是 \(O(\log n)\)，证明的话，考虑将 \(\frac{n}{4}\) 个点变成一个点，分两种情况，该点存在大小超过 \(\frac{n}{2}\) 的子树和不存在。后者已经证毕，每次问题规模有 \(\frac{1}{4}\) 的概率变为原来的 \(\frac{3}{4}\)。前者考虑在该子树中选取包含根的 \(\frac{n}{4}\) 个点重复以上过程，于是不存在大小超过 \(\frac{n}{2}\) 的子树，同样证毕。
基于点分治的原理（独立的子树不跨过分治中心），可以求出每棵子树包含的点集，但如果分治的叉过多，求叉的的过程需要反复尝试每一个叉，复杂度退化到 \(n^2\)。
树形态随机的情况下（随机父亲），每个点的分叉期望是 \(\ln n\) 级别的，复杂度为 \(O(n\log^2 n)\)。
Topsort
需要问树的形态，考虑单独的一次询问能干什么，可以判断一个点是否为叶子，所以考虑从叶子一层一层往上确定。一种比较暴力的方式是先找出所有的叶子，然后删掉后找出二级叶子，找一个点当根，直接确定某个点的父亲是不好做的，考虑为某个点确定一个儿子，方式是二分，重复若干次即可。
确定一层的均摊复杂度是 \(O(leaf\log{(leaf)})\)，外加找叶子的复杂度，总计 \(O(n^2)\)，考虑优化找叶子的复杂度，一种可行的方式是先弄出一个拓扑序排列，按照拓扑序去逐一确定。
弄拓扑序可以考虑以插入的方式构造排列，一个拓扑序合法当且仅当 $ i 满足 j[1,i), p_i 不是 p_j 的祖先$。插入构造时询问一个前缀到根是否包含当前插入的点，如果包含，那么这个点应该放在更前面，得到拓扑序之后就可以逆序构造。
Subtree
考虑递归的构造，确定父亲和子树内容，假设有一个函数 \(f(x)\) 可以求出 \(x\) 子树中所有点的父亲（除自身外），那么调用每个 \(f(x)\) 一次后就可以保证求出树的结构。维护一个没调用过 \(f(x)\) 的点集，在点集中找到一个是 \(x\) 后代的点 \(y\)，调用 \(f(y)\)，于是求出了 \(y\) 后代所有节点的父亲，维护一下没确定父亲点的点集，在没调用过 \(f(x)\) 的点集中，若找不到 \(x\) 的后代，那么就可以开始在没确定父亲的点集中找出 \(x\) 的所有儿子了。
分析复杂度为 \(O(n\log n)\)。