蒟蒻的第一篇题解。由于正值期末周，不想上太大强度，所以匆忙地vp了一场div3，并只出了A~E。
A
白给模拟题，但也是失误很大的一个题(7分钟时才出，属实是太慢了...)
B
一道典题，之前做过类似的。
统计所有数的和sum，只有当sum % n == 0时成立，即每个数最终都必须为sum/n。
注意到最左边的数只能通过靠左位置来变动，所以依次让从左到右的数变为sum/n即可。最后判断末尾的两个数是否经过前面的操作变为了sum/n。
C
数学题，但其实赛时并没有写出正解，而是靠 \(O(n^2)\)暴力 + 卡时限而过的。
一个性质: a是9的倍数 <-> a的所有位数字之和是9的倍数 ，这个性质与3的情况是一样的。
注意到只能操作2，3两个数，且每个数只能操作一次。即：
- 2 -> 4 , 总和加2
- 3 -> 9 , 总和加6
统计串中2，3的个数，则问题变成：有x个2和y个6，问能否通过对其任意选择，使得最后选择的数的总和为9的倍数。
赛时直接暴力枚举了2，6的所有可能的个数情况暴力判断。但其实不需要这样，因为可以发现：当 \(cnt2>=8\) 时，就已经覆盖了所有的可能情况。因为每9个2一定是9的倍数，可以直接提出来模掉，3的情况也同理。所以对于任意>=9个数量的2，它的情况和模9后的数量情况是一样的。因此对于任意\(cnt2\)和\(cnt3\),只需要分别枚举到\(min(cnt2,8)\)和\(min(cnt3,8)\)即可。
D
经典数位贪心题
对于一个数，它的高位数字越大时，无论低位数字的情况，这个数字一定越大。
所以从左到右地考虑左移每一个数字，只要可以让高位变得尽可能大，就进行一次操作，否则停下来并对下一位操作。这样每一步都能让高位尽可能地大，答案也一定是最优解。
E
经典dp模板题
状态定义：\(dp[i][j]\)表示对于串a的前i个字符和串b的前j个字符，能够和c的前\(i+j\)个字符的最大匹配字符数。
则 $ans = lena + lenb - dp[lena][lenb] $
状态转移方程：
dp[i][j] = max(dp[i][j] , dp[i - 1][j] + (a[i] == c[i + j]))
dp[i][j] = max(dp[i][j] , dp[i][j - 1] + (b[j] == c[i + j]))
\(O(n^2)\)转移即可，注意初始化要全面。
F
简单数学 + ST表维护区间gcd
题意是要对于给定的一个区间\([l,r]\),找到一个最大的模数\(m\)，使得对应区间内每个数取模后结果都相等。
对于区间\([l,r]\),需要满足：
a[l] % m = a[l + 1] % m = ... = a[r] % m
考虑任意两个\(x\),\(y\),有：
x mod m = y mod m <==> |x - y| % m = 0
同时注意到，对于区间\([l,r]\)和\(m\),只要每两个相邻元素满足上述关系，则由链式捆绑，上上行的等式关系也一定成立。故m必须是每两个相邻元素差的绝对值的约数。为使\(m\)最大，则\(m\)即为它们的最大公约数。
综上，对于每个区间，答案都是对应区间内所有相邻元素差的绝对值的\(gcd\)。对于q次查询区间，直接ST表维护区间gcd即可。
G
树形dp
状态定义：\(dp[u]\)表示考虑以u为根的子树，从根节点u开始向下删除某条路径，可以得到联通块数量的最大值。
状态转移：考虑u的所有儿子v，现在所有的\(dp[v]\)已经计算完成，要计算\(dp[u]\)。由于只能删除某一条路径，所以要么不选儿子（即只删除节点u，此情况极容易忘记），要么选择其中的一个儿子v并向下走。前者情况即为儿子的个数；后者情况应为（假设删的儿子为v1）：
dp[v1] + cntson - 1
加号后面为常量，若让此式最大化，即找一个最大的\(dp[v]\)转移即可。
现在考虑计算答案：
对于题述的路径的全集，即为所有点的以下三者的总和：
- 从u出发，只选择一个儿子向下走
- 从u出发，选择其中两个儿子向下走
- 只选择一个单独的结点u（即路径上只有这一个点，也是极容易忘记的情况！）
对于1，只需要选择一个最大的\(dp[v]\)即可，但不要忘了u的父亲所在的联通块的贡献（此处还需要额外考虑u有没有父亲，即u是不是根节点）：
max(dp[v]) + cntson - 1 + [u不是根节点]
对于2，需要选择前二大的\(dp[v]\)：
maxfr(dp[v]) + maxse(dp[v]) + cntson - 2 + [u不是根节点]
对于3，即为连接u的结点数量：
G[u].size()
三种情况取最大值即可。最后对于每个点的这三种情况再取一次最大值，即为所有路径的答案。
同时最后还要和1取最大值，因为可能不删结点...