CF2152G Query Jungle（线段树，重链剖分，*）

CF2152G Query Jungle

子树翻转，求没有黑色子孙的黑色点个数。套上 mincnt 标签和双生 rev 标签即可。不明白提交记录里的人都在写什么鬼。

Code

const int inf = 1 << 30;struct Node {int m1 = inf, mc1 = 0, m0 = inf, mc0 = 0;friend Node operator+(const Node& u, const Node& v) {Node w;w.m1 = min(u.m1, v.m1);w.mc1 = (u.m1 == w.m1 ? u.mc1 : 0) + (v.m1 == w.m1 ? v.mc1 : 0);w.m0 = min(u.m0, v.m0);w.mc0 = (u.m0 == w.m0 ? u.mc0 : 0) + (v.m0 == w.m0 ? v.mc0 : 0);return w;}
};struct Tag {int rev = false, x = 0;friend void operator+=(Node& u, const Tag& v) {if (v.x) {u.m1 += v.x;u.m0 -= v.x;}if (v.rev) {swap(u.m1, u.m0);swap(u.mc1, u.mc0);}}friend void operator+=(Tag& u, const Tag& v) {if (v.x) !u.rev ? u.x += v.x : u.x -= v.x;u.rev ^= v.rev;}
};
...
vector<Node> init(n);
folr(u, 0, n - 1) init[dfn[u]] = {sa[u] - a[u], a[u], c[u] - sa[u] - !a[u], !a[u]};
SegTree<Node, Tag> T(init);
auto calc = [&]() {auto tot = T.total();debug(tot.m1, tot.mc1, tot.m0, tot.mc0);return tot.m1 == 0 ? tot.mc1 : 0;
};
cout << calc() << '\n';
int q;
cin >> q;
while (q--) {int u;cin >> u, --u;auto info = T.at(dfn[u]);debug(u, info.m1, info.mc1, info.m0, info.mc0);T.add(dfn[u], dfn[u] + c[u], Tag{true, 0});int delta = info.m0 + info.mc0 - info.m1 - info.mc1;for (int v = fa[u]; ~v; v = fa[top[v]]) T.add(dfn[top[v]], dfn[v] + 1, Tag{false, delta});cout << calc() << '\n';	
}