CF521E

· · 题解

给出一种实现上可能不是非常简洁，但应该很好理解的写法。本题解代码向，思路可以参照其它更加详细的题解。

我用的是在生成树上找被覆盖两次边的做法。前面求生成树森林的部分太简单了就略过，然后我们需要做的就是给一条非树边染色。大概代码是：

for(int i=1;i<=n;i++){
    int x=a[i].x,y=a[i].y;int ll=lca(x,y),color=0;
    while(x!=ll){if(c[x])return found(c[x],i),0;c[x]=i;x=f[x];}
    while(y!=ll){if(c[y])return found(c[y],i),0;c[y]=i;y=f[y];}
}

大概就是说如果发现要染色的边已经染过色了，那么说明肯定存在一种合法解，返回即可。而在 found 函数中，我们需要做的主要有两个：

对于前者有暴力的想法是说给两个环上的点分别染色，这样一来就可以找到两个环的交了。另外同时我们还需要确定起点和终点，发现如果把交的部分抽离出来，起点和终点的度数都是 1，只需要统计一下度数即可。

makeColor(x,cx);makeColor(y,cy);//染色
for(int i=1;i<=m;i++)cc[i]=cx[i]&&cy[i];
for(int wh=1;wh<=m;wh++)
    if(cc[wh])for(int i=head[wh];i;i=e[i].nxt)nowD[e[i].t]++;//统计度数
int px=0,py=0;
for(int i=1;i<=m;i++)
    if(cc[i]&&nowD[i]==1)px==0?(px=i):(py=i);//找到路径的起始点和终点

要输出的三条路径中有一条是很简单的，就是树上的一条路径。于是可以：

vector<int> findPath(int s,int t){
    int ll=lca(s,t);vector<int>ans,rem;
    while(t!=ll)rem.push_back(t),t=f[t];
    while(s!=ll)ans.push_back(s),s=f[s];
    ans.push_back(ll);for(int i=rem.size()-1;i>=0;i--)ans.push_back(rem[i]);
    return ans;
}
inline void printPath(vector<int>ans){
    printf("%d ",ans.size());
    for(int x:ans)printf("%d ",x);
    putchar('\n');
}

剩下的两条路径本质相同，拿一条来说。

红色的点是起始点和终点，蓝色的点是环上的点，发现整条路径可以分成三个部分：px 到 x，x 到 y，y 到 py。那么如何确定哪个是 x，哪个是 y 呢？看图可知，如果一个点 p，满足 dis(p,px)<dis(p,py)，那么这个点是 x，否则是 y。所以在顺序不对的时候需要交换两个点。

int xx=a[x].x,yy=a[x].y;
if(dis(xx,px)>dis(xx,py))swap(xx,yy);
vector<int>an=findPath(px,xx);
vector<int>rem=findPath(yy,py);
for(int wh:rem)an.push_back(wh);
printPath(an);

然后就做完了。由于我太弱了，在写这道题的时候绕了一些圈，所以想要写一篇题解来帮助那些对实现上有困惑的同学（虽然估计没谁会需要呜呜呜）。

最后推销一下博客。