[POI2003] Monkeys 题解
正着做貌似不好做，发现猴子是否掉落取决于“最后一根稻草”，也就是最后撒手的那个猴子，那我们考虑倒着把猴子网拼回去。这样，每群猴子掉落的时刻就是与 \(1\) 号猴子连通的时刻。
利用并查集可以维护猴子的连通性，但是怎么更新答案呢？这里用 vector 进行了一个猴子的存。没错，就是暴力更新，因为每只猴子只会被更新一次；但是合并呢？如果暴力合并复杂度肯定起飞，所以考虑启发式合并，让 \(siz\) 小的向大的上面合并，这样，一个点每被遍历一次，\(siz\) 都会翻倍，时空复杂度都是 \(n \log n\)。
一开始炸空间了还以为是内存管理的问题，后来又 TLE 了才发现是忘了更新 \(siz\) 了，内存管理加不加都无所谓。
代码：
/*
正着很难推，但是如果倒着考虑……
把与 1 联通的时刻作为掉下来的时刻就好了吧
*/
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
int read() {
int x = 0, f = 1; char ch = getchar();
while(ch<'0' || ch>'9') {if(ch == '-') f = -1; ch = getchar();}
while(ch>='0'&&ch<='9') x = x*10+(ch-48), ch = getchar();
return x * f;
}
struct Monkey {
int lh, rh;
bool tagl, tagr;
}a[N];
int n;
vector<int> vc[N];
struct DSU{
int fa[N];
int siz[N];
void init() {
for(int i = 1; i<=n; ++i) {
fa[i] = i;
siz[i] = 1;
vc[i].push_back(i);
}
}
int find(int x) {
if(x != fa[x]) fa[x] = find(fa[x]);
return fa[x];
}
void merge(int x, int y) {
x = find(x), y = find(y);
if(x == y) return;
if(siz[x] > siz[y]) swap(x, y);
fa[x] = y;
siz[y]+=siz[x];
for(int i: vc[x]) {
vc[y].push_back(i);
}
vc[x].clear();
// vc[x].shrink_to_fit();无所谓的内存管理。
return;
}
}dsu;
struct OPT {
int id, op;
}b[N<<1];
int m;
int ans[N];
int main() {
memset(ans, -1, sizeof(ans));
n = read(), m = read();
for(int i = 1; i<=n; ++i) {
a[i].lh = read(), a[i].rh = read();
}
dsu.init();
for(int i = 1; i<=m; ++i) {
b[i].id = read(), b[i].op = read()-1;
if(b[i].op) a[b[i].id].tagr = 1;
else a[b[i].id].tagl = 1;
}
for(int i = 1; i<=n; ++i) {
if(a[i].lh!=-1 && (!a[i].tagl)) {
dsu.merge(i, a[i].lh);
}
if(a[i].rh!=-1 && (!a[i].tagr)) {
dsu.merge(i, a[i].rh);
}
}
for(int i = m; i>=1; --i) {
int x = b[i].id, y = a[b[i].id].lh;
if(b[i].op) y = a[b[i].id].rh;
if(y == -1) continue;
x = dsu.find(x), y = dsu.find(y);
if(x == y) continue;
int tmp = dsu.find(1);
if(x != tmp && y != tmp) {
dsu.merge(x, y);
} else {
if(x != tmp) swap(x, y);
for(int u:vc[y]) {
ans[u] = i-1;
}
dsu.merge(x, y);
}
}
for(int i = 1; i<=n; ++i) {
printf("%d\n", ans[i]);
}
return 0;
}