题解：AT_arc153_f [ARC153F] Tri-Colored Paths

__ACat__ · 2026-09-27 21:18:22 · 题解

摘抄自我的 图论做题记录（点不开说明我未公开）。

AT_arc153_f [ARC153F] Tri-Colored Paths

一道颇具思维量的分讨题。

问题求同时包含三种颜色的简单路径，可以用总方案减去不含这种路径的图的数量。

只含一种颜色和两种颜色的图可以直接算出来，总方案先减去他们俩，得 3^m-3(2^m)+3。

于是我们只考虑三种颜色的情况。

树的情况

在树的情况中，一定形如上图，即存在一个根节点满足他的孩子的子树内都是同种颜色。

于是，我们容易得到，答案为 \sum_u f(\deg_u)，其中 f(x)=3^x-3(2^x)+3。

环内三彩的情况

不是树，就有环呗。

如果环的大小 \ge 4 那么至少存在一个颜色，它有 2 个，于是我们将其中一条这种颜色的边断掉，就出现了含三色的路径。

所以我们只需要考虑三元环。

考虑三元环的外部。

发现如果连出去的边不是在同一点上，那么就只能有一个点是连出去的，颜色为对边颜色，且其他所有边也得是和连出去的边颜色一致（以上图为例，其他边都得是红色，包括未画出的）。

• 所以，每个只有一个连出去的三元环会提供 3!=6 的贡献。

• 如果有两/三个连出去，那就要求连向的是同一点（当且仅当 n=4,m\ge 5 时成立），此时方案数为 3!=6。

环内三彩的情况就考虑完了。

环内二彩

环的外面一定会有其他颜色，且一定可以到达，所以环内二彩的情况 0 贡献。

环内全彩

进一步推得每一个点双联通分量内部颜色一致。

于是我们建出圆方树，按照上述树的情况统计即可。

贡献仍为 \sum_u f(\deg_u)，\deg_u 为 u 在圆方树上的度数，u 为圆点。

于是我们就考虑完了所有情况。