10.14模拟赛总结

T4的欧拉序做法搞明白了，大概意思就是先把问题转化为看这个路径上出现奇数次的边是否刚好是路径长度种颜色，接着进行欧拉序，注意这个欧拉序是进入的时候入序一次，结束的时候再入序一次，然后就是这个有个性质，就是在两点x，y间路径的点就是这个里面x的最后一个到y的第一个或者y的最后一个到x的第一个(看哪个是正着向后的到)，在这个区间里出现奇数次的数再加上LCA就是这个路径上的所有数，利用这个我们不妨对欧拉序上的每个点存下通往它父亲的那一条边，然后当查询x，y时就是统计(x,y)这个区间里的所有出现奇数次的数再加上x，y的影响出现奇数次颜色的种类数（注意不用加上LCA带来的边辣！注意是闭区间里的（下面会说要考虑x,y)!)，这时不妨采用对这个区间的所有颜色异或，首先那些出现偶数次的边会被异或掉，剩下的就会只是在路径上的，然后路径上出现偶数次颜色的也会被异或掉，就只剩下奇数次了，注意这个我们考虑x，y的影响时注意lca(x,y)=x或lca(x,y)=y的情况下只用加上其中一个的影响。