Codeforces 372 Div2
这一次的D题二分收获很大，E题的树分治第一次做。
A. Crazy Computer
题意是给出一个序列，前后差值大于$C$时，结果清空，否则+1，问最终结果。
B. Complete the Word
给出一个字符串，找出含有26个不重复字母的子串，其中?可以替换成任意字符。
C. Plus and Square Root
题意是一个游戏，当前数字是$x$，你可以在$x$的基础上添加任意倍数的$x$，使得在第$k$等上，你要变成的是一个完全平方数，并且它开根号之后，可以被$k+1$整除。
每一轮构造$k*k*(k+1)*(k+1)$，这样开过根号之后变成$k*(k+1)$可以被$k$整除，那么到下一轮，因为有$k+1$这个因子，就可以继续构造$(k+1)*(k+1)*(k+2)*(k+2)$。
D. Complete The Graph
题意是给定一个图，权值为0的边可以任意赋一个大于0的值，要求最终$s$到$t$的最短距离是一个固定长度$L$。
看到这个题最终也可以二分搞，真的是跪服。
二分所有权值为0的那些边的总和，首先如果都为0，那么最短路还大于$L$的GG。都为最大值，最短路还小于$L$的GG。剩下的会发现相当于二分在某一条边上的长度了，dijkstra求最短路。
E. Digit Tree
题意是给定一棵树，每一条边上有一个0到9的数，然后给定一个$M$，满足$gcd(M,10)=1$。现在树上每两点通过边可以得到一个数值$\sum_{i=1}^{k-1}d_{i}*10^{k-1-i}$，问树上任意两点能够被M整除的有多少对。
树分治，首先找重心，然后考虑所有经过重心的有多少对。
假设通过深搜u点的值为123，即在该重心为根的情况下，深度为3。另一个点v的值为45，深度为2。那么能够知道u和v形成的点对的值是12354和45321。那么假设$A$代表从根节点正着计算得到的值，像上面得到的123，45，$B$代表从根节点每一个节点深搜反着得到的值，像321，54。那么被M整除的条件为，
$$
A_u\times 10^{d_{v}}+B_v\equiv 0\ mod\ m
$$
推过来就有
$$
A_u\equiv -B_v \times \frac{1}{10^{d_v}}\ mod\ m
$$
那这样在深搜的时候就知道记录什么了，然后以重心为根，前后深搜两遍，就记录了经过该点的点对数量，之后再接着找重心，分治解。