【八月ex】CF选做
86D
莫队。
移动指针的贡献：\(cnt_i\times cnt_i\times i\)。
600E
Dsu on Tree 的板子之一。
对于轻儿子暴力统计并且每次统计之后删除贡献，重儿子统计后向上不断合并。
对于这个题而言，你需要统计的信息是对于一个点，它的孩子中占主导地位的颜色是哪个，有多少。
52C
简单题。
环形数列，把操作拆成 \([r,n]\)，\([1,l]\) 两部分用线段树维护即可。
617E
莫队。
474F
题意是求一个区间里有几个数能整除区间所有数。
容易发现：
\[\gcd(a,b,c,d)=\gcd(\gcd(a,b),\gcd(c,d))
\]
所以用线段树维护这个东西和有多少即可。
438D
取模操作是 \(\frac{n}{2}\) 级别的 容易得到对于一个区间这样做只需要 \(\log\) 次操作取模就变的很小，判断一下区间和和要模的值即可。
用线段树维护。
484B
二分。
\(\bmod\) 操作可以看作 \(a-\lfloor \frac{a}{b} \rfloor\times b\) 的形式，容易发现 \(\lfloor \frac{a}{b} \rfloor\) 有单调性。枚举 \(b\) 和 \(\lfloor \frac{a}{b} \rfloor\)，二分查找最大的 \(a\) 即可。
1187E
换根dp
一个点的贡献是 \(dp_i=siz_i+\sum dp_v\)，换根，得到换根式子为 \(dp_v=dp_u+n-2\times siz_v\)
609E
对于一张图，我们先找到这个图的最小生成树。
对于最小生成树，每次添加边时，要减去的另一个边的值应该是新添加边形成的环上值最大的一条边。
考虑怎么找这个最大值，对树重剖之后用 ST 表或线段树维护均可。
不能真的把添加的边连上。
570D
Dsu on Tree 的板子之二。
离线先。
统计对于一个点，当前深度字符数量。
能形成回文串，当且仅当奇数字符数量为 \(1\) 或 \(0\)。