提交记录

空间复杂度应该可能大概也许是正常的吧，感觉vector空间常数再大也不至于这么大啊……

做法：将所有操作记录下来倒着加边，用并查集维护。

#include <cstdio>
#include <vector>
#include <cstring>

const int N = 200005, M = 400005;
std::vector<int> sons[N];
int fa[N], ans[N], l[N], r[N], tim, n, m;
struct Edge {
	int u, v;
} e[M];
inline int find(int x) {return fa[x] == x ? x : fa[x] = find(fa[x]);}
inline void join(const int x, const int y) {
	int fx(find(x)), fy(find(y));
	if (fx == fy) {return;}
	if (fy == 1) fx ^= fy ^= fx ^= fy;
	for (int i : sons[fy]) {
		sons[fx].push_back(i);
		if (fx == 1) ans[i] = tim - 1;
	}
	sons[fy].clear(), fa[fy] = fx;
}

int main() {
	scanf("%d%d", &n, &m);
	for (int i(1); i <= n; ++ i) scanf("%d%d", l + i, r + i), fa[i] = i, sons[i] = {i};
	for (int i(1); i <= m; ++ i) {
		int x, y;
		scanf("%d%d", &x, &y);
		if (y == 1 && l[x] != -1) e[i] = Edge{x, l[x]}, l[x] = -1;
		else if (y == 2 && r[x] != -1) e[i] = Edge{x, r[x]}, r[x] = -1;
	}
	
	for (int i(1); i <= n; ++ i) {
		if (l[i] != -1) join(i, l[i]);
		if (r[i] != -1) join(i, r[i]);
	}
	memset(ans, -1, sizeof ans);
	for (tim = m; tim; -- tim) if (e[tim].u || e[tim].v)
		join(e[tim].u, e[tim].v);
	for (int i(1); i <= n; ++ i) printf("%d\n", ans[i]);
	return 0;
}