给你一棵以为根，含有个非叶子节点和个叶子节点的三叉树，每个非叶子节点都有个儿子
所有点的权值只能是或，给定每个叶子节点的权值,，一个非叶子节点的权值与它个儿子节点的权值有关，当它个儿子节点中的个数大于的个数，这个节点权值就是，否则是
有次操作，每次将一个儿子节点取反，你需要在取反后输出号节点的权值
，
可以发现，每次修改后，一定是修改从下往上连续一段，不妨设表示节点的个儿子权值和，那么当时，节点权值为，当时，节点权值为，为了更方便一些，可以假设叶子节点的个儿子权值分别为、和它本身，也用表示，叶子节点的只能为或
那么修改的一定是从要修改的那个叶子节点往上连续一段一样的，再加上一个不一样的
方法一：很容易想到树链剖分+线段树维护，每次修改的是一段链，所以可以先求出序，然后树剖去修改，查询连续一段或，时间复杂度是的，但是因为懒在做专题，所以便没有打了，
方法二：我原本想着用维护一段一样的，放在同一个中，但是怎么搞都没有搞出来，后面在机房神仙的提点下，才知道问题可以转换为找第一个和叶子节点不相同的点
所以可以开一个数组，表示在当前上以为根的子树内深度最大的不为的位置
上传时，先从右儿子得来，如果没有右儿子或者说右儿子没有不为的，那么再考虑自身，最后再考虑左儿子，如下：
inline void push_up(int x)
修改时，找到第一个不为的点，进行单点修改，然后它的右子树内所有点的权值都和当前要修改的叶子节点权值相等，就直接整棵子树全部或者，又由于你要下传首先要满足的就是你的子树内全都是或者,的话全,的话全，相当于是和互换了，所以可以如下方式下传（表示的是懒标记，表示的是权值）：
inline void calc(int x, int y)
{
ad[x] += y, val[x] += y, nt[x][0] ^= nt[x][1] ^= nt[x][0] ^= nt[x][1];
}
inline void push_down(int x)
我感觉这一题难点只要是把维护一段相同的转换为找最后一个不同的，代码实现不会太难，而本蒟蒻刚开始没想到只要和互换就行了，所以开了表示子树内深度最大的权值为，不知道为什么爆零了，改成上述说的才过了
操作都是一些的操作，时间复杂度是的
#include<bits/stdc++.h>
using namespace std;
#define Re register int
const int N = 500005;
const int M = 1500005;
int n, m, l = 1, r, res, g[N], d[N], tr[N][3], q[M], fa[M], val[M], ad[N], son[N][2], nt[N][2];
inline int read()
inline void push_up(int x)
inline void calc(int x, int y)
{
ad[x] += y, val[x] += y, nt[x][0] ^= nt[x][1] ^= nt[x][0] ^= nt[x][1];
}
inline void push_down(int x)
inline bool check(int x)
{
return son[fa[x]][0] == x || son[fa[x]][1] == x;
}
inline void rotate(int x)
inline void splay(int x)
while (check(x))
}
inline void access(int x)
{
for (Re i = 0; x; x = fa[i = x])
splay(x), son[x][1] = i, push_up(x);
}
int main()
for (Re i = 1; i <= n; ++i) push_up(i);
m = read();
while (m--)
val[u] ^= 3;
splay(1);
putchar(48 + (val[1] >> 1)), putchar('
');
}
return 0;
}
