给一个长为 n n n 的序列， q q q 次询问区间 g c d gcd gcd 的个数
线段树维护区间 g c d , m i n gcd,min gcd,min 以及最小值的出现次数，判断区间最小值等于 g c d gcd gcd即可
给一棵树，每个点都是白色，每次可以将一个与黑点相连的白点染成黑色，获得所在联通块的收益，第一次可以任意选点，求最大收益
换根
d
p
dp
dp，考虑固定某个根，则收益为所有儿子
s
i
z
siz
siz 的和
考虑换根，每次将根交换到儿子，发现这两点的贡献会改变，计算下变化的量，转移即可
给一棵树，每个节点有编号从大到小为 A − Z A-Z A−Z，构造一棵树满足任意两个编号相同的节点的路径之中，存在编号比他大的节点
考虑点分治，每次把重心从大到小编号，所有经过重心的路径都可以满足条件，然后分治，最多不超过 l o g log log 层，所以构造方案一定存在
给一棵树，定义 k k k 级表亲为有相同的 k k k 级祖先的节点， m m m 次询问点 x x x 的 y y y 级表亲数量
转化问题，先求出
x
x
x 的
y
y
y 级祖先
f
a
fa
fa，求
f
a
fa
fa 的子树中距离为
d
i
s
[
f
a
]
+
y
dis[fa]+y
dis[fa]+y 的节点个数
将询问离线下来，考虑
d
s
u
o
n
t
r
e
e
dsu\ on\ tree
dsu on tree，用桶统计答案，队列清空，每次处理当前节点的询问即可
n n n 个节点，有 k k k 张边集不同的图，你初始位于 1 1 1 号点，在第 i i i 秒位于第 a [ i ] a[i] a[i] 张图，可以选择走一步 o r or or 不走，求到达点 n n n 的最短时间
最短路问题， t i m e [ x ] time[x] time[x] 表示到达 x x x 的最短时间，考虑边 u → v u\rightarrow v u→v 的转移，枚举存在这条边的图，二分找到从 t i m e [ u ] time[u] time[u] 开始第一次到达该图的时间，取最短时间来转移 t i m e [ v ] time[v] time[v] 即可
n × m n\times m n×m 的矩阵，每个点可能有障碍物 o r or or 额外收益，给 k k k 个起点和 k k k 个终点，选若干条连续的路径，每条路的价值为 100 + 额外收益 − 路径长度 100+额外收益-路径长度 100+额外收益−路径长度，每个点只能出现在一条路径中，不能经过障碍物，求最大收益
数据范围较小，存在若干限制条件，考虑费用流建模，把每个点拆成入点和出点，直接跑最小费用最大流即可
有两种士兵，每种士兵有
n
n
n 个，战斗力分别为
b
[
i
]
,
c
[
i
]
b[i],c[i]
b[i],c[i]，两个不同种类的士兵可以组成一支队伍，战斗力为二者和，可以战胜战斗力比它小的敌人
有
n
n
n 个敌人，战斗力为
a
[
i
]
a[i]
a[i]，战胜后可以得到
p
[
i
]
p[i]
p[i] 的声望，敌人随机出现，求最大期望声望
士兵需要两两匹配，转化为二分图完美匹配，边权为所有战斗力小于他们的敌人可以获得的声望和，直接跑 K M KM KM 算法即可
给一张无向图， q q q 次查询两点的最小割
最小割树板子题，注意无向图建边要建四条
给一张有向无环图，每条边花费一定的代价 a [ i ] a[i] a[i]，每条边至少走一次，每次从 1 1 1 号点出发，可以在任意点结束，求最少代价
板子题，建超级汇点，每个点和超级汇点连边，然后限制每条边的下界为 1 1 1，上界为 i n f inf inf，跑有源汇上下界最小费用可行流
给一张有向无环图，每次可以走图上一条链，求最少几次把图全部遍历完
板子题，考虑网络流建模，建超级源汇+虚拟源汇，每条边至少走一次，考虑限制下界为 1 1 1，上界为 i n f inf inf，然后跑有源汇最小可行流
给 n n n 个点， m m m 条边，问如果最小生成树必须包含第 1 ≤ i ≤ m 1 \le i \le m 1≤i≤m 条边时的最小权值和
先建出最小生成树，然后对这棵树树剖 o r or or 树上倍增，枚举所有边，查询在生成树上的链上最大值即可
给一棵树， q q q 次查询，每次给两个点，求到这两点距离相等的点的个数
倍增 l c a lca lca，每次找他们的中点减去在两条链上的 s i z siz siz 即可