（多数都是水题
最优贸易
缩点，拓扑排序，然后考虑 $dp$ 出 Mn 表示 $1$ 到这个位置的最小买入价格，然后用在下一个位置卖出的收益更新一下 $dp$ 。
其中 $dp[u]$ 表示 $1 \to u$ 路径上最大的差价，用上面说的方式更新即可。
Road Construction
缩边双，会得到一个树，不难发现链接两个点就把这两个点所在边双在树上的路径给合并到同一个边双。
然后发现拿叶子最优，然后可以猜结论答案是叶子个数除以二上取整。
每轮找公共祖先最靠上的缩起来就好了。
矿场搭建
考虑缩点双，求法大概是先求割点，然后从非割点开始 dfs ，不经过割点得到的连通块就是点双。
考虑缩点双后会由割点的形式连成一个树，如果一个点双度数为 $2$ 那么显然随便炸哪里都可以跑。
否则如果是叶子，那么内部需要选非割点的点作为出口。因为即使这个出口被炸了，也可以跳到父亲。
如果整个连通块是同一个点双，必须在内部建两个出口，不然一个出口被炸了就没救了。
Chessboard
考虑黑白染色后一个多米诺骨牌必然跨一个黑点一个白点，建二分图后跑最大匹配即可。
航线规划
随时都是树，我们可以倒着做，相当于在树上加边，然后求两点之间的桥数量。
加边相当于把这两个点之间的点合并到一个点双。可以看成最开始所有边都是白色，每次选择两个点把这条路径染黑。
由于每个边只会被染黑一次，拿并查集维护这个点向上的第一个白色边的位置即可。
我们可以对每个位置维护出这个位置到根的白色边数量，然后染色就是一次区间修改。区间改单点查直接 BIT 即可。
Prime Set
毒瘤题。
可以发现如果不考虑 $2$ 那么一个素数必然是由一个偶数一个奇数组成。我们把偶数和奇数放在两边，相当于是二分图最大匹配。然后我们考虑最大匹配如果不到 $k$ 那么就尝试加入最大匹配之外的数即可。如果我们求的最大匹配是 $a$ ，那么答案就是 $2a + k - a$ 这个东西，但是不一定真的所有数都可以加进去，我们与所有有边的点的数量和取 $\min$ 即可。因为这个东西就是不考虑限制匹配个数时的答案的上界。
但是考虑 $1$ 的存在，两个 $1$ 也可以连成素数，也就是说我们要在匹配尽量大的同时保证 $1$ 用的尽量少。一种简单的想法是费用流。但是有一种优秀做法（从网上学来的不知道为啥对），不加 $1$ 并且跑一次最大匹配，然后加入 $1$ 再跑，差值就是尽量少用的 $1$ 。
Muddy Fields
考虑极长的竖段和横段。一个位置要么被它所处的竖段覆盖要么被横段覆盖，从一个点的竖段向横段连边后就是二分图的最小点覆盖。
最小点覆盖就是网络上的最小割，等于最大匹配。
食物链
拓扑排序后直接 $dp$ 即可。
最后只统计没有入度的位置的答案，去除一个点的链，一个没有出度的位置的初值设 $1$ 。
阿狸和桃子的游戏
看到这题猜一下能不能把权值放到点上。
然后发现最优化的是差值，直接把边权给放到两个点上，再给点权两倍一下，然后如果一条边的两边被不同的人选择，对差值没有贡献，否则就是给一个人了这条边两倍的权。
然后答案就是排序后交替选的差值除以二。
这题为啥黑啊喂
CF1349C Orac and Game of Life
我们考虑每个大小大于 $1$ 的连通块，不难发现每一回合连通块内部颜色必然反转一次。大小等于 $1$ 的则不会反转。
当一个大小大于 $1$ 的连通块处于一个大小等于 $1$ 的连通块旁边时，则会 ”同化“ 这个大小为 $1$ 的连通块。
于是我们从大小大于 $1$ 的连通块开始跑 $\text{bfs}$ ，跑出每个点第一次被同化的时间即可。
一个点被同化之后每轮都会跟着开始复读 $010101\dots$ ，取模即可。
AGC032C Three Circuits
考虑如果存在一个点度数为奇数，那么明显无解。
否则，如果存在一个度数 $\ge 6$ 的点，从这个点整出去的 $3$ 个环就可以拿出来。
否则，我们考虑度数为 $4$ 的点的数量：
没有，一个环，显然不行
只有一个，就是两个简单环拼起来，肯定画不出来。
正好两个，那么要么是这种情况：
这种情况明显是可以构造出三条欧拉回路的。（注意，这里的 $4,5,2,3,6,7$ 都可能是很多点，但是这些点度数为 $2$ 所以没有讨论的必要）。
还有：
这种是不能构造的。
多于 $2$ 个
考虑对于第一种情况中随意加环，明显可以构造。
对于第二种情况中，必然是除开 $1,6$ 外某个点有 $4$ 的度数，那么我们图上的这两个环删掉后必然还剩至少一个环。于是一定可以构造。
然后判断这两种情况，就看是否可以不经过另一个度数为 $4$ 的点走出一个环即可。
CF875F Royal Questions
经典套路：二分图上度数为 $2$ 的点，看成是出边的两个点间的边。然后选择一个边就得确定一次顺序，使得每个点出度为 $1$ 。这个东西本质上就是找一个基环树森林。然后这个东西大概是一个拟阵，然后从大到小加边，并查集维护当前的基环树即可。
ARC093C Bichrome Spanning Tree
我们考虑一棵最小生成树，设它的权值为 $Y$ 。
分类讨论一下：
$X < Y$
无解。
$X = Y$
考虑分两种情况。我们随意求的这棵最小生成树，如果我们给它染上不同的颜色，那么无论其余的边如何染色，都一定有这棵生成树合法。答案是 $( 2^{n - 1} - 2 ) \times 2^{m-(n-1)}$
如果我们给它染上相同的颜色，我们给剩下的边分成两类，一类是加入这条边并删除这个边路径上的最大边后不会导致答案变化，这种边的数量是 $a$ ，另一类是加入后并删除这条边路径上的最大边后就导致这个生成树变变大了，称为 $b$ 。
不难发现 $a$ 边不能都和生成树颜色一样， $b$ 边任意染色。这部分答案是 $2(2^a-1)2^b$
$X > Y$
考虑这种情况下，所有最小生成树，以及加入一条边后使得生成树大小不到 $X$ 的边都必须和最小生成树染同一种颜色，不然直接选择这一种边后生成树大小就小于 $X$ 了。剩下的边，如果加入后就使得生成树大小变成了 $X$ ，这种边就是之前的 $a$ 类边，不能全部和生成树颜色一样的。如果加入后使得生成树 $> X$ ，那就是之前的 $b$ 类。
答案仍然是 $2(2^a - 1)2^b$ 。
AGC033C Removing Coins
先画下链的情况，发现要么选叶子要么选里面，分别给链的长度减少 $1,2$ 。
然后考虑一般情况，于是猜了个结论：一直选择直径即可，于是写了发按照直径长度模三分类，然后就奇迹般地过掉了 。
不难发现选择树内任意一个除叶节点操作本质相同，都会使得直径长度减少 $2$ 。而直径是最长的路径，必然是最后被减没了，也就是最后剩下的点一定再直径上，所以要么选择直径中的点，要么选择直径叶点。