这题很明显是lct,我们只要可以维护黑色点深度和即可。
但是lct维护子树信息好难写啊。
首先边权比较难处理,所以偷懒加虚点表示边。然后考虑维护子树距离和,需要维护splay上的边权和。
为了可以reverse,还必须维护一个反的距离和。 虚子树的答案更新在access和link连虚边的时候。 好烦啊。千万不要把splay之前的下传标记写挂,记得只下传本splay的标记。
#includeusing namespace std;typedef long long ll;const int N=200005;struct node{ int blcnt;//black cnt int non_cnt;//xzs ll non_dis; ll sumval;//bian quan he int val;//bian quan ll disl,disr;//disl disr bool fl,bl; int fa,ch[2]; void clear(){ memset(this,0,sizeof(*this)); } void print(){ cout<<"blcnt: "< <