模拟赛。T1 太难不会，做了 T2；T4 打了暴力。
\(0 + 100 + 0 + 30\)，没挂分，不知道rk多少，排名好像极其差劲
T2
给定序列 \(a\)，每次可以选一个区间把他从小到大排序，求能不能变成 \(b\) 并输出方案
\(n\le 10^3\)，操作次数不超过 \(n^2\)。
考虑直接选一个长区间显然不比只交换两项强。所以直接冒泡排序。
T3
给序列 \(a\)，计数字典序不大于他、数不超过 \(m\) 且和相同的序列。
\(n \le 10^3, a_i \le m \le 10^3\)
那还说啥了。
考虑二项式反演，一个经典的模型（可惜我不知道）是求有多少个 \(a_i\in[0,m), \sum a_i = s\) 的方案数。设这个是 \(f(n,s)\)。
钦定 \(k\) 个 \(\ge m\)，那么把他们减掉之后剩下的均分 \(s-mk\)。那你就隔板。
\[f(n,s)= \sum_{k=0}^n (-1)^k\binom{n}{k}\binom{s-mk + n - 1}{n - 1}
\]
然后预处理 \(a_i\) 的后缀和 \(s_i\)，答案是
\[\begin{aligned}
&\sum_{i=1}^n\sum_{t=0}^{a_i-1}\sum_{k=0}^{n-i} (-1)^k\binom{n-i}{k}\binom{s_i - t -mk + n - i - 1}{n - i - 1}\\
&=\sum_{i=1}^n\sum_{k=0}^{n-i} (-1)^k\binom{n-i}{k}\sum_{t=0}^{a_i-1}\binom{s_i - t -mk + n - i - 1}{n - i - 1}
\end{aligned}\]
然后最里面的和式只跟 \(t\) 有关，上指标求和即可。
T4
边点都带权，选两个点 \(x, y\)，最小化 \(\sum_\limits u \min (\rm{dis}(u,x), \rm{dis}(u,y))\)
\(n \le \times 10^5\)
先讲 30pts。考虑断边，然后取重心即可。
然后 100pts 我也不特别懂，大概就是用这个东西表示子树答案：
\[\sum_{(u,\rm{fa}(u))\in E}w\min(siz_u,siz_1-siz_u)
\]
然后用数据结构去维护取到哪个。