1. Campus Partition
Source：ICPC 2023 Hefei
首先可以想到，连通块可以简化为：最大的两个值在端点的路径。
于是乎子树内至多会有一条路径向上走，那么可以进行 DP，设 \(f_{u,i}\) 表示这条路径向上对应的另一个端点权值是 \(i\)，\(g_u\) 为子树内完整把路径走完。
有转移：
\[\begin{aligned}
f_{u,i}=\max(f_{u,i}+g_{v},\sum_w g_w+f_{v,i})\\
g_{u}=\max(g_u+g_v,f_{u,i}+f_{v,j}+\min(i,j))
\end{aligned}
\]
直接 DP 即可做到 \(O(n^2)\)。
\(f\) 后续的 \(i\) 只会有 \(n\) 个，使用线段树合并维护整个 DP 数组，具体的手法是：
- 对于 \(f\)，首先给 \(u\) 下边全局加 \(g_v\)，\(v\) 下边全局加 \(\sum_w g_w\)，合并即可。
- 对于 \(g\)，前者是简单的，后者则需要在合并过程中，枚举每个 \(j\)，讨论 \(j\) 是 \(f_{v,j}+j\) 还是 \(f_{v,j}\)，值域线段树中维护一个前后缀 \(\max\) 即可。
由此做到 \(O(n\log n)\)，Submission。
2. The only winner
Source：9th BSUIR Open Semifinal
枚举唯一最大值 \(s\)，那么对于 \(2n\) 而言，\(<s\) 有 \(s-2n-1\) 种取法，此后 \(2n-1\) 除去发现贡献是相同的，也是 \(s-2n-1\)。
还需 pick 出一个值使其取到 \(s\)，这个值共有 \(n-(s-2n)/2\) 种取法。
其余的随意匹配即可，还有 \(2(s/2-n)\) 个数，所以剩下 \((2(s/2-n)-1)!!\)。
所以分子即为 \(\sum (s-2n-1)^{n-(s-2n)/2-1}(n-(s-2n)/2)(2(s/2-n)-1)!!\)。
分母显然是 \((2n-1)!!\)，预处理双阶乘即可做到 \(O(n\log n)\)，记得特判 \(n=1\)，Submission。