题解
由易到难,先不考虑交替的事情,既然要尽量少的涂色,那么我最少要涂几条颜色的边?(由于图不一定联通,这里先考虑连通图的情况)
如果一条边处于一个环内,那么这个边就可以不涂色。
所以只要有环我就可以选择一条边不涂色,那么到最后,涂色的边构成一棵树
接下来考虑这颗树能否实现红蓝交替
要满足红蓝交替,则要满足对于任意两点 \(u,v\),\(u \to lca(u,v)\),\(v \to lca(u,v)\) 的边是交替的,且 \(lca(u,v)\) 通向两点的第一条边颜色不同
满足前半个条件很简单,按深度奇偶性涂色
一条灰色边对应一个环,无向图dfs生成树一定满足上述限制,即生成树中上述情况不可能存在
code
标签:P10298,S4,2024,交替,涂色,lca,CCC
From: https://www.cnblogs.com/pure4knowledge/p/18211754