赛时吃了三个法师，不过问题不大。
赛时
AB 简单字符串处理。
C 中需要满足：
- \(m=n-1\)
- 只有两个度数为 \(1\) 的点，剩下点的度数都为 \(2\)。
- 记得判连通！！
D 根据题目要求观察发现，每一次匹配都是 \(S\) 的一个前缀和 \(T\) 的一个前缀匹配，\(S\) 的一个后缀和 \(T\) 的一个后缀匹配，且前缀长度递增，后缀长度递减。
于是考虑预处理出 \(S\) 和 \(T\) 的最长公共前缀和最长公共后缀，然后考虑每一个答案，若需要的前缀比最长公共前缀长，需要的后缀比最长公共后缀短，即满足条件。
E 经典 trick，将所有字符串 sort 排序，答案必定诞生在相邻字符串之间，依次查找更新即可。
F 树形背包，观察数据范围，考虑 \(O(n^2)\) 做法。
考虑设 \(dp_{i,j,0}\) 表示以 \(i\) 为根的子树中，\(i\in V\)，且一共被分成了 \(j\) 个连通块的方案数；\(dp_{i,j,1}\) 表示以 \(i\) 为根的子树中，\(i\notin V\)， 且不包括 \(i\) 所在的连通块的情况下一共被分成了 \(j\) 个连通块的方案数。根据题目要求，有如下转移方程：
\[dp_{u,j+k,0}=\sum_{v\in son_u} dp_{u,j,0}\times dp_{v,k,0}\\ dp_{u,j+k+1,0}=\sum_{v\in son_u} dp_{u,j,0}\times dp_{v,k,1}\\ dp_{u,j+k,1}=\sum_{v\in son_u} dp_{u,j,1}\times (dp_{v,k,0}+dp_{v,k,1}) \]最后 \(ans_i=dp_{1,i,0}+dp_{1,i-1,1}\)。
G 考虑权值线段树。离散化所有权值后，维护权值区间的权值和与个数和。
对于操作 \(1\)，将原权值所在位置单点修改，并将新权值位置单点修改。
对于操作 \(2\)，将权值所在位置进行单点修改。
对于操作 \(3\)，线段树上二分即可。
注意数组不要开小，线段树值域大小包括了操作的值域。
H 赛后再补。
标签：Atcoder,连通,前缀,Beginner,后缀,sum,287,权值,dp From： https://www.cnblogs.com/ydtz/p/17071338.html