既然是YNOI那肯定是要分块的。先考虑树是一条链的情况，可以直接回滚莫队，对n个节点组成的序列分块。在回滚莫队的过程中，当前维护的区间一共会扩展\(O(n\sqrt n)\)次，每次都是合并了恰好2个连通块。可以用线段树合并对每个连通块维护其中颜色的奇偶性。注意到每次合并，都有其中一个连通块的大小是1，这就保证了复杂度，\(O(n\sqrt nlogn)\)。
然后再来看树不是链的情况。这是再用上面的方法复杂度就假了，因为这时加入一个点可能会合并不止一个连通块。对所有边组成的序列分块也不行，因为线段树合并和撤销的复杂度不能保证。那我们应该对其他什么东西分块才对。
考虑这样一件事情：把节点1~n从左到右排成一行，然后从右到左一个个把节点加入维护的区间，并进行连通块之间的线段树合并。令\(c_i\)表示加入第i个点时，线段树合并内部进行的操作次数。线段树合并的时候不是要递归吗，每次递归都算一次操作。显然，\(\sum{c_i}=O(nlogn)\)。接下来用数组c对1-n组成的序列进行"加权"然后分块跑莫队，也就是把i号点复制\(c_i\)份，形成一个长度\(O(nlogn)\)的序列，然后对它回滚莫队。这时候发现复杂度就对了，不会出现不均匀的情况。
线段树合并常数太大了，考虑使用压位trie。也就是一个类似这样的结构：
时间复杂度还是\(O(n\sqrt nlogn)\)级别的，常数小了不少。
标签：洛谷,分块,题解,线段,合并,Ynoi,nlogn,莫队,复杂度 From： https://www.cnblogs.com/legendstane/p/luogu-p-6580-ynoi-solution.html