BZOJ3319 黑白树

异常欢乐的并查集。馒头染色法。均摊O(n)的时间。

离线，先把每个染色操作会染黑哪些边算出来，把黑色子节点并到白色父节点里。

然后倒着处理，询问就直接用并查集问白色子节点顶上的黑色父节点最近是谁。染色操作再染回来。

#include <cstdio>

#include <cctype>

#include <cstring>

#include <algorithm>

using namespace std;

struct edge {

int t, i;

edge *next;

};

struct query {

int t, v, ans;

int *b;

};

int _d_;

#define readInt(_x_) { \

int& _s_ = _x_; \

_s_ = 0; \

while (!isdigit(_d_ = getchar())); \

while ((_s_ = _s_ * 10 + _d_ - 48), isdigit(_d_ = getchar())); \

}

const int maxn = 1000009;

int n, m, d[maxn], fa[maxn], v[maxn], c[maxn], r[maxn];

int i_buf[maxn], *tib;

query q[maxn];

edge *head[maxn], *ep;

inline void addEdge(int u, int v, int w) {

ep-> t = v;

ep-> i = w;

ep-> next = head[u];

head[u] = ep ++;

}

void buildTree() {

static int q[maxn];

int hd = 0, tl = 1;

memset(d, 0, sizeof(d));

memset(c, 0, sizeof(c));

d[1] = 1;

fa[1] = 0;

fa[0] = 0;

r[0] = 0;

v[0] = 0;

v[1] = 0;

q[hd] = 1;

while (hd < tl) {

int p = q[hd ++];

for (edge* e = head[p]; e; e = e-> next)

if (!d[e-> t]) {

d[e-> t] = d[p] + 1;

fa[e-> t] = p;

v[e-> t] = e-> i;

q[tl ++] = e-> t;

}

}

}

int getRoot(int x) {

int p, q;

for (p = x; r[p] ^ p; p = r[p]);

for (; x ^ p; q = r[x], r[x] = p, x = q);

return p;

}

int lca(int u, int v, int* a) {

int t = 0;

u = getRoot(u);

v = getRoot(v);

while (u ^ v) {

if (d[u] > d[v]) {

a[t ++] = u;

c[u] = 1;

r[u] = getRoot(fa[u]);

u = r[u];

}

else {

a[t ++] = v;

c[v] = 1;

r[v] = getRoot(fa[v]);

v = r[v];

}

}

return t;

}

int main() {

#ifndef ONLINE_JUDGE

freopen("in.txt", "r", stdin);

#endif

readInt(n);

readInt(m);

memset(head, 0, sizeof(head));

ep = new edge[n * 2];

for (int i = 1; i < n; ++ i) {

int u, v;

readInt(u);

readInt(v);

addEdge(u, v, i);

addEdge(v, u, i);

}

buildTree();

tib = i_buf;

for (int i = 1; i <= n; ++ i)

r[i] = i;

for (int i = 0; i < m; ++ i) {

readInt(q[i]. t);

if (q[i]. t == 1) {

readInt(q[i]. v);

}

else {

int u, v;

readInt(u);

readInt(v);

q[i]. b = tib;

q[i]. v = lca(u, v, q[i]. b);

tib += q[i]. v;

}

}

for (int i = 1; i <= n; ++ i)

if (c[i])

r[i] = i;

else

r[i] = fa[i];

for (int i = m - 1; i >= 0; -- i)

if (q[i]. t == 1)

q[i]. ans = v[getRoot(q[i]. v)];

else {

for (int j = 0; j < q[i]. v; ++ j) {

int p = q[i]. b[j];

r[p] = getRoot(fa[p]);

c[p] = 0;

}

}

for (int i = 0; i < m; ++ i)

if (q[i]. t == 1)

printf("%d\n", q[i]. ans);

}