题意
给定一个 \(n\) 个点 \(m\) 条边的无向连通图，求将 \(m\) 条边进行 \(3\) 染色且满足：
存在一条简单路径，使得路径上三种颜色的边各有至少一条。
的方案数。数据范围：\(n,m\leq 2\times 10^5\)。
做法
这题思路非常的自然其实，不知道为啥群友都不会做。
首先容易想到这种题可以正难则反，即求不存在满足条件的简单路径的染色方案数。我们称这样的染色方法合法。
一个一般图的简单路径太多，不好处理，但是发现如果是一棵树的话就会看上去简单很多。首先尝试去向树靠近。
注意到一般图和树的区别在环，考察一个环的染色情况。
Observation \(1\)：如果存在一个长度 \(\geq 4\) 的环包含全部 \(3\) 种颜色，那么这种染色一定是不合法的。
证明：找到一条颜色重复的边然后断开这个环就能找到一个满足条件的简单路径。
对于 \(3\) 色环有很好的性质，但是一张图不一定存在 \(3\) 色环，这让我们很苦恼。
Observation \(2\)：一个满足每种颜色的边至少有一条的染色方案必然有至少一个 \(3\) 色环或全为同色环。
证明：
考虑一个 \(2\) 色环，注意到一个环的环长 \(>2\)，且这个环外面一定有一条第三种颜色的边。
手玩一下可以发现必然可以找一条边断环然后连到外面那条边，组成一个合法路径。
所以存在 \(3\) 色环或只存在同色环。
我们分两种情况讨论：只存在同色环 或 存在 \(3\) 色环（它的长度必定是 \(3\)）。
对于第一种情况，容易证明染色的形态是：一个割点将图分成了多个部分，每个部分里的边颜色相同\(^1\)。
我们令 \(f(x)\) 为将 \(x\) 个球染成 \(3\) 种颜色且每种颜色至少出现一遍的方案数。
可以发现这种情况的贡献为 \(\sum_vf(cnt_v)\)，其中 \(cnt_v\) 是 \(v\) 将图分成的连通块个数。
对于第二种情况，容易证明染色的形态是：一个大小为 \(3\) 的 \(3\) 色点双，外面仅挂着一棵子树，这棵子树里面的边颜色与和它不相邻的点双中的边颜色相同\(^2\)。
这种情况的贡献为 \(6C\)，其中 \(C\) 是大小为 \(3\) 的点双的个数。
于是只需输出 \(f(m)-\sum_vf(cnt_v)-6C\) 即可。复杂度容易做到线性。
彩蛋
当你愉快的写完之后你会发现你过了后两个样例，但是前两个样例挂掉了。但是你先别急。
因为仔细观察之后可以发现，我们的证明在 \(n\leq 5\) 的时候是伪证。
幸运的是，对于 \(n\leq 5\) 的情况我们可以用暴力解决。
\(1:\) 证明待补。
\(2:\) 证明待补。
标签：Tri,Paths,存在,颜色,染色,路径,证明,ARC153F,色环 From： https://www.cnblogs.com/Kevin090228/p/17065609.html