题目传送门：CodeForces 1555F Good Graph
Statement：
定义一张图为好图当且仅当图中所有简单环的\(xor\)为\(1\)。按顺序给定\(q\)条边，边权\(\in\{0,1\}\)。初始图上无边，按顺序依次考虑每条边，若这条边加入后图依旧是好图，那么可以加入，否则不能加入。输出每条边是否加入。
\(n,q\leq 3\cdot10^{5}\)
Solution:
可以发现图中一定不存在两个环有公共边。
那么一开始把改变联通性的边先加入，这样显然不影响答案。
加完后图变成了森林，再依次考虑构成环的边。
若\(u\)到\(v\)的路径上已经存在一个环了，那么这条边不能加入，否则加入并且把\(u\)到\(v\)路径上的边打上标记。
边上打标记显然可以转成向点打标记。
这样看上去要树剖，但是认真分析后可以发现每条边只会被加人一次，也就是每个点只会被加人一次，那么可以用DFS序的树状数组维护子树加，查询链和。
时间复杂度为\(\mathcal O(Q\log_2N)\)。