由于莫队是一种毒瘤的数据结构，而且最近一直在练莫队的扩展，所以就把练习的题目放到这里面。

还没更完，咕。

经典根号分治。

题意转化为给你一颗树，每个节点有颜色，每次询问有多少个颜色为 $r1$ 的点 $e1$ 是颜色为 $r2$ 的点 $e2$ 的祖先。

萌新刚学根号分治系列

根号分治，即把一个问题分成两类，一类是规模小于 $\sqrt{n}$ 的，一类是规模大于 $\sqrt{n}$ 的。当然这个阈值有时候可能为了常数乃至复杂度需要调整。

如果没有任何限制，那么插板可得方案数就是 $\tbinom{n-1}{m-1}$。

对于大于等于的限制，这种情况直接把 $m$ 减去 $A_i-1$ 即可。

$A$

何老板有 $n$ 根大小相同且质地均匀的火腿肠，要分给 $m$ 名信竞队员。要求每名队员分得的香肠重量相同。
何老板想知道，最少切多少刀就能满足上述要求？

阅读全文 »

套路推式子题好像还挺无脑的啊。

规定 $n<m$。原式珂以等于这一坨。

果然练了两个多月图论还是那么菜啊。

$A$

给你一个 $n$ 节点 $m$ 条边的无向图，无向图中可能存在“环”(回路)。

阅读全文 »

非常腻害（？）的一个科技，前缀优化建图。

首先看到”每条边至少有一个端点是关键点”珂以想到 2-SAT，对于每个点建立两个点 $x_1,x_2$ 分别表示 $x$ 不是关键点和是关键点。

假装我在写总结，实际上是题解

本题缺少 $\sum t_i$ 的范围，必须人肉二分数组大小才能通过，建议管理员加上。

最小割经典题。