AGC
AGC补完计划:1/37
AGC001
C - Shorten Diameter
题意:给定一棵$n$个点的树，每次删掉一个叶子结点，询问最少删除几次，使得最后得到的树的直径小于等于$m$。$n,m\le 2000$。
题解:对于一棵树，当它的直径为偶数时，它的中心是一个点，否则是一条边。如果我们想删除一些点得到一棵直径小于等于$m$的树，我们把距离中心大于$\frac{n}{2}$的点都删掉即可。所以枚举中心然后dfs一遍得到深度即可。
复杂度$O(n^2)$
D - Arrays and Palindrome
题意:给定一个$A$序列，让你重排这个序列，并构造另一个序列$B$。
满足:
- $\sum A_i=\sum B_i$
- 对于一个字符串$\text{S}$，如果$S_{1,A_1},S_{A_1+1,A_1+A_2},\cdots,S_{1,B_1},S_{B_1+1,B_1+B_2},\cdots$都为回文串，那么使得$\forall i,j,A_i=A_j$
题解:当奇数个数大于$2$时，没有解。这样两个奇数块放在两端，将中间的偶数块用长度$-1$的$B$回文来连接。
E - BBQ Hard
题意:求$\sum\sum C_{a_i+b_i+a_j+b_j}^{a_i+a_j}$。$n\le 200000,a_i,b_i\le 2000$。
题解:考虑$C_{a}^{b}$的组合意义是从$(0,0)$点走到$(a,b)$的方案数