A
Solution
特判 l=r=1l=r=1l=r=1 的情况输出 111，其余情况答案均为 r−l+1r-l+1r−l+1。
B
Solution
考虑翻转一个子序列对 [l,r][l,r][l,r] 的和的贡献。很明显，若翻转的这个子序列，其左右端点分别在 lll 左侧，rrr 右侧，则左右端点对 [l,r][l,r][l,r] 区间都不会有贡献。因此只有两种情况：
* [1,l−1][1,l-1][1,l−1] 的一些数和 [l,r][l,r][l,r] 的一些数做了交换
* [r+1,n][r+1,n][r+1,n] 的一些数和 [l,r][l,r][l,r] 的一些数做了交换
很明显肯定每一次是拿 [l,r][l,r][l,r] 区间中最大的换对面区间最小的，因此直接模拟即可，时间复杂度为 O(nlogn)O(n\log n)O(nlogn) 瓶颈在排序。
Another Problem：如果翻转的是一个连续的子序列，那么应该怎么做？
C
Solution
考虑删除一个点 uuu 对树连通块的贡献。
* 若删除该点之后树为空，则连通块数量为 000。
* 否则，删除该点后连通块数量会增加 degu−1\deg u-1degu−1。其中 degu\deg udegu 表示 uuu 点当前在树上的度数。
因此考虑枚举第一个点删除的是哪里，然后直接计算出第二个点删除哪里最优。具体的说，枚举删除第一个点 uuu 之后，uuu 点的 deg\degdeg 会清零，而对于所有的 vvv 满足 TTT 中存在 <u,v> 一条边，vvv 点的 deg\degdeg 都会减 111。此时很显然只需要取 deg\degdeg 最大的点即可。显然可以用线段树搞，时间复杂度为 O(nlogn)O(n\log n)O(nlogn)。
D
Solution
首先考虑若某一行上有 a,b,c,da,b,c,da,b,c,d 四个点（a<b<c<da<b<c<da<b<c<d），而另一行上至少有两个点。现在我们需要恰好选两个三角形把 a,b,c,da,b,c,da,b,c,d 选完，则：
* 若两组分别选择 a,ba,ba,b 和 c,dc,dc,d，则对答案的贡献为 b+d−a−cb+d-a-cb+d−a−c
* 若两组分别选择 a,ca,ca,c 和 b,db,db,d，则对答案的贡献为 c+d−a−bc+d-a-bc+d−a−b
* 若两组分别选择 a,da,da,d 和 b,cb,cb,c，则对答案的贡献为 c+d−a−bc+d-a-bc+d−a−b
其中二、三两种选择方法的值比第一种优秀。因为第三种最好处理所以全部选择第三种取法。
因此我们处理出两个序列 c,dc,dc,d 分别表示 a,ba,ba,b 两个序列按照上述左右选的贪心方法能够得到的贡献。显然此时 c,dc,dc,d 两个序列均严格单调递减。而若此时选择 iii 个数，则必然在 ccc 序列中选 kkk 个数，ddd 序列上选 i−ki-ki−k 个数。显然肯定从前往后选答案最大。因此贡献即为 ∑j=1kci+∑j=1i−kdi\sum\limits_{j=1}^k c_i+\sum\limits_{j=1}^{i-k}d_ij=1∑k ci +j=1∑i−k di 。容易观察到这个东西随 kkk
的变化是单峰的，因此使用二分或者三分都可以通过这个题，时间复杂度为 O(nlogn)O(n\log n)O(nlogn)。
E
Solution
可以简单证明 f(i,j)=2min(dist(u,lca),dist(v,lca))−1f(i,j)=2\min(\text{dist(u,lca),dist(v,lca)})-1f(i,j)=2min(dist(u,lca),dist(v,lca))−1，但是这个式子直接算最多只能做到 O(n2)O(n^2)O(n2)，因此考虑拆分之。
f(i,j)=2min(dist(u,lca),dist(v,lca))−1=2min(depu−deplca,depv−deplca)−1=2min(depu,depv)−2deplca−1\begin{aligned} f(i,j)&=2\min(\text{dist}(u,\text{lca}),\text{dist}(v,\text{lca}))-1\\ &=2\min(\text{dep}_u-\text{dep}_\text{lca},\text{dep}_v-\text{dep}_\text{lca})-1\\
&=2\min(\text{dep}_u,\text{dep}_v)-2\text{dep}_\text{lca}-1\\ \end{aligned} f(i,j) =2min(dist(u,lca),dist(v,lca))−1=2min(depu −deplca ,depv −deplca )−1=2min(depu ,depv )−2deplca −1
这样看起来舒服多了！答案即为
∑i=1n∑j=i+1nf(i,j)=∑i=1n∑j=i+1n[(i, j) is good](2min(depu,depv)−2deplca−1)=2∑i=1n∑j=i+1n[(i, j) is good](min(depu,depv)−deplca)−n(n−1)2=2∑i=1n∑j=i+1nmin(depi,depj)−2∑i=1n∑j=i+1ndeplca(i, j)−n(n−1)2+∑i=1n∑j=i+1n[(i, j) is not good]\begin{aligned}
\sum\limits_{i=1}^n\sum\limits_{j=i+1}^nf(i,j)&=\sum\limits_{i=1}^n\sum\limits_{j=i+1}^n[\text{(i, j) is good}](2\min(\text{dep}_u,\text{dep}_v)-2\text{dep}_\text{lca}-1)\\ &=2\sum\limits_{i=1}^n\sum\limits_{j=i+1}^n[\text{(i, j) is
good}](\min(\text{dep}_u,\text{dep}_v)-\text{dep}_\text{lca})-\frac{n(n-1)}{2}\\ &=2\sum\limits_{i=1}^n\sum\limits_{j=i+1}^n\min(\text{dep}_i,\text{dep}_j)-2\sum\limits_{i=1}^n\sum\limits_{j=i+1}^n\text{dep}_\text{lca(i, j)}-\frac{n(n-1)}{2}+\sum\limits_{i=1}^n\sum\limits_{j=i+1}^n[\text{(i, j) is
not good}]\\ \end{aligned} i=1∑n j=i+1∑n f(i,j) =i=1∑n j=i+1∑n [(i, j) is good](2min(depu ,depv )−2deplca −1)=2i=1∑n j=i+1∑n [(i, j) is good](min(depu ,depv )−deplca )−2n(n−1) =2i=1∑n j=i+1∑n min(depi ,depj )−2i=1∑n j=i+1∑n deplca(i, j) −2n(n−1) +i=1∑n j=i+1∑n [(i, j) is not good]
此时等式被分为了四个互相独立的部分，考虑分开求解：
* 2∑i=1n∑j=i+1nmin(depi,depj)2\sum\limits_{i=1}^n\sum\limits_{j=i+1}^n\min(\text{dep}_i,\text{dep}_j)2i=1∑n j=i+1∑n min(depi ,depj )：考虑对 dep\text{dep}dep 数组从小到大排序，此时 ∀i,j∈[1,n],i<j,depi≤depj\forall i,j\in[1,n],i<j,\text{dep}_i\le\text{dep}_j∀i,j∈[1,n],i<j,depi ≤depj 。答案即为
2∑i=1n∑j=i+1ndepi=2∑i=1ndepi∑j=i+1n1=2∑i=1ndepi(n−i)2\sum\limits_{i=1}^n\sum\limits_{j=i+1}^n\text{dep}_i=2\sum\limits_{i=1}^n\text{dep}_i\sum\limits_{j=i+1}^n1=2\sum\limits_{i=1}^n\text{dep}_i(n-i)2i=1∑n j=i+1∑n depi =2i=1∑n depi j=i+1∑n 1=2i=1∑n depi (n−i)。
* 2∑i=1n∑j=i+1ndeplca(i, j)=2∑lca=1n∑i=1n∑j=i+1n[lca(i, j)=lca]deplca=2∑lca=1ndeplca∑i=1n∑j=i+1n[lca(i,j)=lca]2\sum\limits_{i=1}^n\sum\limits_{j=i+1}^n\text{dep}_\text{lca(i, j)}=2\sum\limits_{\text{lca}=1}^n\sum\limits_{i=1}^n\sum\limits_{j=i+1}^n[\text{lca(i,
j)}=\text{lca}]\text{dep}_{\text{lca}}=2\sum\limits_{\text{lca}=1}^n\text{dep}_\text{lca}\sum\limits_{i=1}^n\sum\limits_{j=i+1}^n[\text{lca}(i, j)=\text{lca}]2i=1∑n j=i+1∑n deplca(i, j) =2lca=1∑n i=1∑n j=i+1∑n [lca(i, j)=lca]deplca =2lca=1∑n deplca i=1∑n j=i+1∑n [lca(i,j)=lca]。问题变为计数对于每一个
lca\text{lca}lca，有多少对 (i,j)(i,j)(i,j) 使得 lca(i,j)=lca\text{lca}(i,j)=\text{lca}lca(i,j)=lca。考虑树上 dp 得到 sizi\text{siz}_isizi 表示以 111 结点为根，iii 点子树的大小是多少。那么显然只有子树内选点才能使得其 lca\text{lca}lca 为 iii，答案为 sizi(sizi−1)2\dfrac{\text{siz}_i(\text{siz}_i-1)}{2}2sizi (sizi −1) 。但是这个可能会多统计答案。因此对于 iii 的每一个儿子结点
jjj，都需要容斥掉 jjj 子树内选两点的答案 sizj(sizj−1)2\dfrac{\text{siz}_j(\text{siz}_j-1)}{2}2sizj (sizj −1) 。因为树上所有点的儿子结点的数量是 O(n)O(n)O(n) 级别的，因此该部分时间复杂度也为 O(n)O(n)O(n)。
* n(n−1)2\dfrac{n(n-1)}{2}2n(n−1) ，这个直接算就行了。
* ∑i=1n∑j=i+1n[(i, j) is not good]\sum\limits_{i=1}^n\sum\limits_{j=i+1}^n[\text{(i, j) is not good}]i=1∑n j=i+1∑n [(i, j) is not good]。因为 (i,j)(i,j)(i,j) 是 not good\text{not good}not good 的，当且仅当 iii 是 jjj 的祖先或 jjj 是 iii 的祖先。因此考虑让 i,ji,ji,j 无序，此时只需要计数 iii 是 jjj 祖先的方案数即可。显然 iii 是 jjj 祖先的时候，jjj 只能在
iii 的子树内取，有 sizj\text{siz}_jsizj 种方案。因此答案即为 ∑i=1nsizi\sum\limits_{i=1}^n\text{siz}_ii=1∑n sizi 。
于是这个问题就解决了，时间复杂度为 O(nlogn)O(n\log n)O(nlogn)，瓶颈在于第一步的对 dep\text{dep}dep 从小到大排序。
Code
F1
Solution
首先考虑每一个位置任意选择左括号 / 右括号，答案是多少。显然一个长度为 2n2n2n 的序列而言，不同的合法序列数为 Catalan(n)\text{Catalan}(n)Catalan(n) 即卡特兰数第 nnn 项，答案为 (2nn)/(n+1)\binom{2n}{n}/(n+1)(n2n )/(n+1)。问题是目前确定一些位置为左括号，一些位置为右括号，方案数是多少。此时可以把序列分为若干段。这个地方画图解释：
其中相同颜色的部分为一组，一组之内可以任意匹配括号，但是需要保证每一组的所有括号单独拿出来还是匹配的。
因此可以用栈线性模拟出每一个不同颜色块的长度，然后对每一段单独计算卡特兰数，使用乘法原理将其相乘。因为组合数 / 逆元都可以在 O(n)−O(1)O(n)-O(1)O(n)−O(1) 时间复杂度内预处理 / 求解，所以总时间复杂度为 O(n2)O(n^2)O(n2)，可以通过。
Code
F2
暂时不会，下午更新
