因为有个人说我选的题目太难了，所以我决定把难度控制在黑题以下，于是全部选择了一些紫题。
下面可能会用到一些知识，别担心都是学过的和一些概念，如果不会那么事后可以去看看：
CF1680F
如果原图是二分图，那么直接进行染色即可，下面考虑不是二分图的情况。
因为一个图是二分图的充要条件不存在奇环，所以为了将一个不是二分图的东西进行染色，需要找到一条边满足所有的奇环都经过这条边而且没有偶环经过。
之所以需要没有偶环，是因为选择的这条边两侧的颜色是一样会的。
这样就相当于经过这条边不改变颜色，所以原本的偶环就只会经过奇数条改变颜色的边，也就相当于是奇环了。
现在需要找到一条被所有的奇环经过且没有被偶环经过的边，或者报告无解。
容易想到给所有的奇环和偶环分别染色，最后遍历每一条边，如果满足条件那么就有解。
考虑对图进行一个类似于 Tarjan 的操作，跑出一个 dfs 树。
因为所有的环肯定是经过了若干条树边和一条非树边，所以就可以在遍历树的同时处理非树边即可。
具体的，可以通过树链剖分的方式处理树边，对于非树边直接暴力修改即可。
对于只有一个奇环的情况并不需要特判，因为这个情况非树边必然满足被所有的奇环经过而且没有偶环经过。
时间复杂度为 \(O(m+n\log n)\)。
CF1515G
在一个有向图中，因为要从 \(p\) 出发然后再回到 \(p\)，所以路程只能在包含 \(p\) 的强连通分量里面。
那么容易想到先用 tarjan 跑出强连通分量，然后对于每一个强连通分量分开求解，下面的所有讨论都在一个强两连通分量之内。
另外因为这个题目要求对 \(t\) 取模，所以一下所有的操作都是在模意义之下的。
首先有两个个性质：
如果存在一条路径 \(a\to b\)，而且边权为 \(w\)，那么就可以构造出 \(b\to a\) 而且边权为 \(-w\) 的路径。
证明：
因为 \(a,b\) 在同一个强连通分量内，所以它们必然在一个环中，假设这个环的边权和为 \(s\)。那么从 \(b\) 出发绕着环走 \(t\) 圈，这样的贡献就是 \(s\times t\) 也就是 \(0\)。
所以只要在最后一圈的时候直接停在 \(a\) 那么就相当于构造出了一条 \(b\to a\) 的边权为 \(-w\) 的路径。
另外有一个性质，如果强连通分量上有一个环，那么所有的点都可以看作在这个环上。
证明：
假设 \(a\) 在长度为 \(x\) 的环上，而 \(b\) 不在。
假设 \(a\to b\) 的路径长度为 \(w\)，那么根据上面的性质，显然 \(b\to a\) 的长度就是 \(w\)。
那么就可以构造 \(b\to a\to b\) 的路径，在到达 \(a\) 之后可以随意的在环上行走，而结束后又可以原路返回。容易理解，这样路径的长度为 \(w+x+(-w)=x\)。
那么我们假设这个强连通分量中，所有的环的大小为 \(x_1,x_2,\cdots,x_{ct}\)，那么如果需要有解显然需要满足：
\[{\sum\limits_{i=1}^{ct} k_i\times x_i}\equiv s\pmod{t} \]其中 \(k\) 满足：
\[\forall i\in[1,ct]\cap \mathbb{Z}\mid k_i\in\mathbb{Z} \]那么根据裴蜀定理，有：
\[\gcd\limits_{i=1}^{ct} x_i\mid s \]所以现在的问题就转化成为了统计一个强连通分量内所有的环的长度的 \(\gcd\)。
显然，直接求出所有的环显得并不现实，因为原本环的个数时无限的，所以考虑只求解出一些环但是其 \(\gcd\) 却与原本一样。
容易发现只有简单环对答案有贡献，因为不是简单环的一定都是几个简单环的和，而 \(\gcd\) 有性质 \(\gcd(a,b)=\gcd(a,b,a+b)\)，所以注定时不影响答案的。
为了以防有人不会证，这里说一下：
设 \(\gcd(a,b)=g\)，那么 \(a=\dfrac{a}{g}\times g\)，\(b=\dfrac{b}{g}\times g\)，所以就有 \(a+b=g\times ({\dfrac{a}{g}+\dfrac{b}{g}})\)。
对于统计环的情况，在这个强连通块中构建出一个 dfs 树，显然环有两种情况：一条非树边和一些树边组成，多条树边和一些树边组成。
显然对第二种情况，这些环的长度都可以通过第一种环通过加减得到，所以显然不会对 \(\gcd\) 产生影响。
于是就遍历这个 dfs 树，如果遇到了返祖边那么就更新 \(\gcd\) 于是就做完了，时间复杂度为 \(O(n\log V)\)。
标签：图论,乱讲,gcd,连通,偶环,那么,奇环,分量 From： https://www.cnblogs.com/liudagou/p/18634256