这是道好题啊。。。想想麻烦。。做做更麻烦。。

题目很简洁，给你一个图，求哪些边删掉之后能变成二分图。。

额。。我WA了N次。。比赛的时候肯定来不及。。。

慢慢分析吧。。

首先求生成树，然后对每个点2-染色，

那么如果删非树边的话，显然任何点的颜色都不会变，那么如果两端颜色一样的非树边有0条，所有非树边都可以删，有1条，只有这条可以删，2条或以上，都不能删。。

如果删树边的话，显然必须要搞翻所有的奇环，分析一下什么情况下一个树中会出现奇环。。

某个两端颜色一样的非树边造成的奇环。。

一个两端颜色一样的非树边和一个两端不一样的非树边造成的奇环。。

那么把这个树树链剖分一下。。对每个两端颜色一样的非树边的两点之间的路径+1，显然要删的树边上的权值一定要等于非树边的数量。。

然后对每个两端颜色不一样的非树边的两点之间的路径+1，显然要删掉树边不能在被两端颜色一样的非树边的两点间的路径跨越的情况下再被这个不一样的非树边的两点之间的路径跨越。。

然后维护两个树链剖分。。分别搞树边和非树边。。就没什么问题了。。

写的累死晕。。。**我发现还是我在codeforces上英文的说明更清楚一点啊囧。。。It’s a interesting problem.If you for every edge, try to remove it and check if it is a **bipartite

graph..I think it will get TLE..so let’s analysis

the property of bipartite graph..

It should never contain a cycle of odd length…

and it can be 2-colored..

so first build a spanning forest for the graph..

and do the 2-color on it(Tree can be 2-colored).

for convenience.

Let TreeEdge={all edge in forest}

NotTreeEdge={All edge}/TreeEdge

ErrorEdge={all edge that two endpoint have the same color..}

NotErorEdge=NotTreeEdge/ErroEdge..

First,consider a edge form NotTreeEdge,remove it

can’t change any node’s color..so..if |ErrorEdge|=0 of course we can remove all NotTreeEdgeif =1 we just can remove the ErrorEdgeif >1 we can’t remove any from NotTreeEdge

Now,Let consider a Edge e from TreeEdge..

Let Path(Edge e)=the path in forest between e’s two endpoints..

if there is a Edge e’ from ErrorEdge that Path(e’)

didn’t go through e..it will destroy the bipartite

graph..

if there is a Edge e’ from ErrorEdge that Path(e’) go through e and there is a Edge e” from NotErrorEdge that Path(e”) go through e..it will also destroy the bipartite graph..

so now we need to know for every edge,how many such path go through it..it require a data structure…

one way is to use heavy-light decomposition then we can update every path in O(LogN^2)…

another way is to use Link-Cut Tree..It can do the same in O(LogN)….

Code：

http://www.ideone.com/dPS5N

你在ideone上交程序交错语言了……

回复中国脑筋：汗。。。果然是的。。我去修改一下。。。

http://www.ideone.com/dPS5N上面那个交错语言了。。Chrome不方便修改。。。只好先放在留言板里。。

回复WJBZBMR：chrome是方便修改的……

回复中国脑筋：Chrome一打开编辑就是一堆乱七八糟的HTML代码囧。。。

回复WJBZBMR：代码是能看懂的……又不是乱码……

恩,不错.不过我先看的是英文版的.

always i used to read smaller content that

also clear their motive, and that is also

happening with this post which I am reading here.