省选成功成为河北B队队长QAQ 真是忧桑
所以在cojs上出了一套鬼畜的关于树的套题
黑白树：
我们先不考虑R操作
设x是u的祖先，那么fa(x)的贡献显然是 fa(x)*(sz(fa(x))-sz(x))
之后我们对于这个求和就是答案辣
然而这一脸不可做，我们化简一下，考虑每个sz(x)的贡献
sz(x)的贡献化简后可以发现 为 (x-fa(x))*sz(x)
然后我们就很容易用树链剖分完成更改和查询操作啦
之后我们考虑R操作
因为树上距离公式为 dis(u)+dis(v)-2*dis(lca(u,v))
最后一项为偶数，显然对奇偶性没有影响
那么当dis(u)为奇数时，这个操作等价于将所有dis值为偶数的点翻转
dis(u)为偶数时同理
又注意到对于R操作最多只会有4种形态
奇偶都不翻，奇偶都翻，奇翻偶不翻，奇不翻偶翻
不妨建立四颗线段树分别维护这四种形态
每次更改将四颗线段树都更改，查询在对应情况下查询即可
这样R操作我们可以O(1)的更换查询的线段树进而完成更改
树黑白：
这套题中最水的一道 目前为止我知道两种做法
第一种做法是动态点分治
对于每一层的重心维护子树中黑点到他的距离和和子树黑点个数
还要维护子树中黑点到他父亲的距离
这样每次查询我们只需要加上当前层的贡献，减去父亲层的贡献就可以啦
更改的时候暴力更改相关的子树就可以了
第二种做法是树链剖分
树上距离公式dis(u)+dis(v)-2*dis(lca(u,v))
显然sigma(dis(u))和tot*dis(v)我们都是已知量
问题就变成了维护dis(lca(u,v))
我们考虑每条边的贡献，设这条边的边权为w，儿子一端为x
那么贡献就是w*sz(x)
用树链剖分维护即可，做法跟黑白树差不多
树白黑：
首先我们考虑如果没有[L,R]的做法
我们可以用DFS序+树状数组维护子树和
每次修改单点加减
之后对于查询我们从查询点向上倍增
跳到离u最近的祖先且子树和不为0的位置
这个位置显然就是答案
之后我们发现子树和是具有可减性的
那么做法就很显然了，用DFS序+主席树维护
继续沿用上面的做法就可以了
白黑树：
数据很难做，最后也做得不是很成功
我们考虑树链剖分
对于每次修改，我们可以将u到根节点所有值+1或者-1
这样我们会发现父亲节点的值一定>=孩子节点的值
而当父亲节点的值>孩子节点的值的时候，显然存在一个黑点和当前点的LCA为这个父亲节点
我们定义这样的情况为一个分界点，那么显然我们要求的是深度最小的分界点
可以发现这个分界点一定是u到根节点路径中的最大值的位置
当然值相同的点我们要取深度较大的点
之后我们就可以利用树链剖分完成链修改和链查询了
UPD_1：神一样的lyc提供了一种更好的做法
我们会发现深度最小的LCA的子树一定恰好包含所有黑点
那么问题就是求离u最近的包含所有的黑点的祖先
跟树白黑一样倍增即可
UPD_2：这样子的话和树白黑一样也可以加大这道题目的难度
可以把解法变成主席树之类的奇怪的东东
不过数据就更加难出了，所以还是这样子吧