最近多校补题的时候连着做了两个题，发现它们的内核惊人地相似，所以写一篇来总结一下（可能是久违的复活文）。
想看结论可以直接看结尾

－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－

2021暑期多校解题报告
0tree
题意：给出一棵带有点权a（非负整数）和边权e（整数）的树，可以做若干次如下的操作：选择两个不同的结点x, y和一个非负整数w，将x, y的点权各自异或w，将x->y路径上的边权依次+w, -w, +w, ..., (路径长度为偶数以-w结尾，奇数以+w结尾)，问是否可以在4n次操作以内将所有的点权和边权变为0。可以的话输出方案。
n<=10000，点权和边权的绝对值在1e9以内。

分析：
1. 首先，单独考虑异或操作，可以将问题转变为：对于一棵树，每次同时将任意两个结点的权值异或w，问是否可以将整棵树的权值变为0。
不难发现这个时候树的结构没有起到任何作用，和相同的问题在序列上的效果是一样的。＃可以发现当且仅当所有结点的权值a异或和为0的时候，可以在O(N)的规模下将所有结点的权值变为0＃（选取一个点为参考点，依次将它和其他任意点i同时异或上点i的权值）。因为同时异或两个点，所以所有点的权值异或和是不变的，故当把除参考点以外的所有点权值变为0之后，如果所有点的疑惑合为0，那么参考点的权值也应该为0，否则不存在方法可以让所有的点权值为0。
2. 考虑关于边权的操作，显然直接按照题目描述的操作来说过于复杂了，一次操作涉及到的对象太多，不利于我们思考问题。于是考虑简化操作，将边权转化为点权，即令一个点的和点权b等于与它相连的所有边权的和。
接下来我们证明，#所有边权等于0等价于所有和点权b等于0#：
假设当和点权为0的时候，存在边权不为0。显然我们可以发现，如果叶子结点的点权等于0，那么其父边的边权一定为0，又因为父亲的和点权为0，那么父亲的父边为0......如此，递归地证明了必要性；
假设边权全部为0，那么显然和点权b为0，证明了充分性。
那么，问题转化为是否可以让所有点的和点权为0。注意到，当x->y链长为奇数的时候，x+w, y+w；链长为偶数的时候，x+w, y-w，因此操作按链长的奇偶性分类。基于这一点想到给树分层（二分染色）。可以发现每次操作相当于是重新分配了同色层的b，对于异色层则是同时增大了权值。于是我们可以注意到，和点权可以全部为0等价于和点权的和小于等于0且奇偶层的sumb相等（参考1中参考点的做法证明这个想法）。
3. 现在分开地考虑了两个问题，考虑将两个问题合并起来。我们考虑先将所有的点权a变为0，现在问题变为：在不改变a的情况下，如何让所有的b变为0。
考虑不改变a的条件。由于是异或操作，因此只要异或两次就不会改变a。那假设在将所有的b变为0的过程中保证这个条件，就是考虑将忽略a的情况下只需要进行一次的操作|b|拆分成两个2 * |b|/2，于是我们要求b的值一定要是一个偶数。
注意到本题的操作分别是异或和求和，当他们的一个参数(w)相同的时候，会注意到结果的奇偶性变化是同步的（w为奇，改变奇偶，w为偶，奇偶不变）。因此可以发现所有点a b奇偶性一致是可以让所有点权和边权为0的必要条件。在这个基础上，可以发现当所有的a都为0的时候，因为a与b的奇偶性一致，那么b必然为偶数。因此就可以将一个操作正确地拆分成两个相同的操作了。

综上，可以将所有的点权和边权同时归零等价于三个条件：
1. 所有点权a异或和为0。
2. 两色层各自和点权b的和<=0，并且相等。
3. 每个点上a与b的奇偶性相同。
输出方案的时候，对于奇偶层各自选取一个参考点，先把所有的点依次与自己所在层的参考点成对操作，然后操作两个参考点。重复两次即可，可以在3n次以内完成。

power station of art
题意：现有一种图（不保证连通），点有编号，点上有数字和颜色(R, B)，可以进行任意次操作：选择一条边<u, v>交换u, v上面的数字，如果u, v上面的颜色相同，那么翻转颜色；如果颜色不同，那么不变化。现在有两张结构一样的图（即点集边集相同，但是点上的数字和颜色不同），问是否可以通过若干次操作（可以不操作），使得两张图完全一样？输出YES或者NO。

分析：
依旧分开考虑两种操作：
1. 对于交换数字，可以发现只要两张图连通分量点上值的集合相同，那么就可以使得两张图相同。显然这是充要条件。
2. 对于交换颜色，题目中的操作依然显得有一点晦涩。因此等价地理解题意：将两个点的颜色交换，然后翻转。这样就统一了问题。
注意到这是一个二色的问题，对于图我们联想到二分图，因此我们按照二分图来讨论问题。
2.1.如果连通分量是二分图。可以发现当交换两个点的时候，集合的颜色(w/h)和点的颜色(r/b)是同时变化的。考虑一个不变量------颜色的异或始终不会发生变化。那么显然，两张图中的(number, pointcolor^graphcolor)二元组的集合应该完全相同，两张图上的点形成一个单射。这显然是一个充要条件。
2.2.如果连通分量不是二分图，这意味着图中至少含有一个奇环。考虑这个奇环可以做什么------可以固定上面所有点的数字，而使得两个相邻点的颜色发生变化（1按次序交换到n，再与2交换，然后2反向地交换回1的旁边）。
同时，注意到一个必要条件------两张图连通分量上的颜色数量的奇偶性必须相同（因为无论操作是那种情况颜色数量的奇偶性都不会改变）。
这意味着，利用奇环的这个性质可以让环上所有点同时变成我想要的颜色（先挨个变化，剩下最后两点的时候，以为颜色的奇偶性是相同的，因此一定可以操作过去）。
在满足两个必要条件的情况下，考虑这样一种策略：对两张图上的点做一一映射。如果一个点不在任何的简单奇环里面，我们就让它换到奇环和它在的块连通的那个点，把它变成想要的颜色，然后处理其他的点，使得它在自然到达它映射的点的时候变成自己想要的颜色。然后再通过奇环的特殊性调整环上的值和颜色（如果觉得不好理解那就把图简化成基环树，就很好理解了）。
这样，我们证明了非二分图只要满足两个必要条件即可完成目标。

综上，可以将两个图变得相同，等价于：
1. 所有连通分量对应的点上数值集合相同。
2. 所有的连通分量：
2.1. 是二分图，则（数值，pointcolor^graphcolor）二元组集合相同。
2.2. 不是二分图，则r/b两色数量的奇偶性对应相同。

总结：
回过头来看两题，可以发现它们在表面上完全不相关，但是仔细思考可以发现它们的内核惊人地相似：

1. 对图的两个点进行操作
2. 操作可逆
3. 操作同时修改两种属性，形成约束
4. 操作的效果和奇偶相关

根据2，容易想到寻找操作中的不变量。因为操作可逆，如果不变量相同，那么这两种情况就形成了等价类。第一题中的向参考点简化，第二题中二分图部分的处理都运用到了这一点。
根据3，我们在思考时可以考虑是否存在一种方案，使得保持一个属性不变的同时改变另一个属性。第一题中最后b的归零，第二题中奇环部分性质都运用到了这一点。
根据4，图的奇偶性可以考虑到二分图。根据二分图将问题进行分类，往往可以让问题变得易于思考。二分图本身有非常好的性质，而非二分图又有奇环，因此可以很好地考虑问题。

同时，在补这两个题的过程中，注意到对于一张图上的操作不好思考的时候，可以考虑更强的树/基环树上的操作。这样问题变得更加见解，而且如果命题在强环境（注意树这样的环境是强是弱要根据问题来判断）下成立，那么在弱环境的图上就一定成立。
而且在问题看起来复杂的时候，可以通过一些简单的转化把问题转化成简单易懂的版本。统一性可以更好的帮助我们解决问题。