Description：

给一棵三叉树，每个点的输出 $0/1$ 由他的子树中 $0/1$ 的个数谁多决定，带修改询问根节点输出。

$1\leqslant n\leqslant 5\times 10^5$

Solution：

不难想到用 $LCT$ 维护，但是考虑怎么维护，那么我们可以给每个点定一个权值 $0/1/2/3$ 表示子节点的输入和，发现每修改一个叶子节点会产生变化的一定是从这个点往上走的一部分链，而且一定是连续的一段 $1$ 或 $2$ 还有最上面那一个点，那么我们就可以用两个变量维护某个点上方最长的一段 $1$ 或 $2$ 的信息，具体来说就是在每个点分别维护最深的不是 $1$ 或 $2$ 的点，把他转到根对它进行单点修改，然后对右子树整体修改。整体修改其实就是 $1$ 变 $2$ 相当于用 $3$ 减。

Code：