Codeforces #405(Div. 2) - Click Here
Preface
又是一个万年老坑，赶紧填上QAQ。
Problem A(CF791A)
Solutions
$a$和$b$辣么小，直接模拟即可。
CODE
CODE - Click Here
Problem B(CF771A)
Solutions
画几个图再连下边就会发现，满足要求的充要条件是，每个连通分量的边均为$\frac {N(N-1)}{2}$。
DFS判断每个联通分量是否符合即可。
CODE
CODE - Click Here
Problem C(CF771B)
Solutions
从左到右的每个相邻区间，都是增加一个节点，减小一个节点。
因此区间的两个边界节点(即最左侧的节点和最右侧节点)只会在该区间产生影响，那么这个两个点就可以瞎搞了。要是$No$，则两个节点相同；要是$Yes$，则两者不同。
CODE
CODE - Click Here
Problem D(CF771C)
Solutions
题目求的是$\sum_{i=1}^n \sum_{j=i+1}^n f(s,t)$，该式等价于$\frac{\sum_{i=1}^n \sum_{j=1}^n f(i,j)}{2}$，因此现在的问题就是如何求出$f(i,j)$。
不妨先假设$k=1$，此时问题变成求任意两点的距离之和，即求出任意一个点到其他所有点的距离和。
令点$i$到达其他所有点的距离和为$S_i$，而$S_i$可以分成$i$子树内所有点的距离和，和非$i$子树内所有点的距离和。由此我们可以得到一个求解该问题的一个DP做法。
即令$f[i]$表示$i$子树内所有点的距离和，$g[i]$表示非$i$子树内所有点的距离和。
显然可得转移方程
$f[i]=\sum_{j \, is \, the \, son \, of \, i}(f[j]+size[j])$
$g[i]=g[fa(i)]+(n-size[fa(i)]+1)+\sum_{k \neq i}(2*size[k]+f[k]), \, k \, is \, the \, son \, of \, fa(i)$
其中$size[i]$表示$i$子树节点数大小，$fa(i)$表示$i$的父亲节点。
但是，这题的$k$不为1。如何解决？
首先思考一个问题，那就是$k>1$后会产生什么影响。即要求出$f(i,j)$与$k$的关系。
根据简单的贪心思想，容易得到$f(i,j)=\lceil \frac{dis(i,j)}{k} \rceil$，这个式子表明每走$k$步答案增加1。
那现在让我们思考一下什么时候答案会被更新。首先对于任意$dis(i,j)$，必定可以写成$ax+b,b \in [1,k]$的形式，当然$0$除外。此时$\lceil \frac{dis(i,j)}{k} \rceil=\lceil \frac{ax+b}{k} \rceil=x+1$，也就是说答案会被更新，当且仅当$b$从$k$变成了$1$，只有在这种情况下$x$才会发生变化。
基于这种思想，可以在DP时存储$b$为$[1,k]$个数。
因此得到一个新的DP做法。
即令$f[i][j]$表示$i$子树内所有点的距离的$b$分别为$[1,k]$的个数，$sf[i]$表示子树内距离和。同理，可以定义$g[i][j]$以及$sg[i]$。
特别的，用$f[i][0]$表示$i$子树中，距离为0的节点个数(即$i$节点本身)。
利用与$k=1$做法相似的思路，可以得到其转移方程，此处不再写出。
最后时间复杂度$O(NK)$。
But…
上诉做法太过麻烦，虽然时间复杂度优秀(比题解优)，但由于$f[i][0]$的存在，使得特殊情况特别多。(花了我半节数学课去完善DP)
那有没有什么简单易懂的做法呢，显然是存在的。
上诉做法是以点作为出发点得到的，现在让我们以边为出发点思考。
同样的，从$k=1$开始思考。路径是由边组成的，而边的数量又与距离等价，因此若能够求出每条边经过次数，那加起来的答案就是距离了。
具体的做法是枚举每一条边，看这条边左边以及右边的节点数，两者相乘就是经过次数了。
设这个答案为$S$。
现在思考$k>1$的情况，此时的距离公式变成了$f(i,j)=\lceil \frac{dis(i,j)}{k} \rceil$。之所以不能够直接将$\frac{S}{k}$作为答案，是因为存在某些距离不能被$k$整除。若所有距离都能够被$k$整除，那么$\frac{S}{k}$作为答案就是正确的。
因此，可以对那些无法整除的距离进行“补充”，即加上一个数字使得$dis(i,j)$即能够对$k$整除，又不会对答案造成影响。也就是说，最后的答案会变成$\frac{S+\sum tot[L]*(k-L\, mod \,k)}{k},L \, mod \, k > 0$，其中$tot[L]$表示距离为$L$的总个数。
但是实际上，我们并不关心距离为$L$的个数，我们只关心$L \, mod \, k$的个数，因为$L$被整除部分已经在$S$中体现了。
那如何求出个数？
首先需要知道$dis(i,j)$的求法，即$dis(i,j)=dep[i]+dep[j]-2*dep[LCA(i,j)]$，其中$dep[i]$表示节点$i$的深度，$LCA(i,j)$表示$i$与$j$的最近公共祖先。
基于这个式子，只需要枚举$LCA(i,j)$，以及$dep[i] \, mod \, k$以及$dep[j] \, mod \, k$的数值就好了。
时间复杂度$O(NK^2)$。
CODE
CODE(以点为出发点) - Click Here
CODE(以边为出发点) - Click Here
Problem E(CF771D)
Solutions
除了$V$和$K$以外的一切字符，我们并不关心其字母是什么。因此对于非$V,K$的字符一律可以当成$X$。
接着，其最后的答案必定是多组$V+X+K$组合的形式(当然，不完整的结构也是可行的。比如$X+K$或者$V+X$的结构)，而且最后答案的前$v$个$V$，前$k$个$K$，前$x$个$X$必定是原字符串中的前$v$个$V$，前$k$个$K$，前$x$个$X$。
基于这两个性质，容易得到其DP做法。
即设$f[v][k][x][the \, last \, letter \, is \, V]$，表示用前$v$个$V$，前$k$个$K$，前$x$个$X$组成新字符串的最小交换次数。为了防止$V$和$K$对接的情况，还需要记录最后一位是否为$V$。
转移方程也很显然，就是枚举新加入的字符是$V$，$K$还是$X$。由于转移方程过于繁琐，此处不写出。
那如何计算对答案产生的贡献？不妨假设从$f[v][k][x]$转移至$f[v+1][k][x]$。根据上面给出的性质，原字符串中的第$v+1$个$V$将要前移。而在前移之前的前$v$个$V$，前$k$个$K$，前$x$个$X$已经以某种顺序排好了。现在需要前移的这个$V$只需要跨过不属于已经排好序的字母即可，这个扫一遍即可求出。
最后总时间$O(N^4)$。
CODE
CODE - Click Here