看到这种题应该想到的是树状数组。
树状数组+二分来求解mex问题是个经典的trick。
考虑直接用树状数组来存储周围的点，发现不可做：对于一个点如果度数过大在反复修改的时候就会时间爆炸。
现在我们有两种做法：暴力和树状数组+二分。
前者的修改时间复杂度低查询时间复杂度高而后者相反。
容易想到根号分治。
由于瓶颈在于点的度数所以对点的度数进行根分，如果大于阀值则开树状数组，小于则暴力修改。
嗯，这就是正解，但卡常。
那我不想卡常怎么办。
直觉告诉我们这个 \sqrt n 大抵去不掉。
那就把$\log n$ 去掉。
这个 \log n 是由bit带来的，所以想想把bit改成其他数据结构。
我们发现在修改的时候要进行$\sqrt n$次运算而查询的时候只要 \log n 级别。
那我们就把他换成分块吧，修改 O(1) 查询 O(\sqrt n)
但是这个时间复杂度还是没变。
唉对啊，为什么用了分块还要二分，暴力跳块就行了。
很好你得到了一个 O(n\sqrt n) 的做法。
核心代码：
while (q--) {
int opt, u, x;
io.read(opt);
io.read(u);
if (opt == 1) {
io.read(x);
for (vi::iterator it = imp[u].begin(); it != imp[u].end(); it++) {
B[*it].update(a[u], -1);
B[*it].update(x, 1);
}
a[u] = x;
} else if (opt == 2) {
if (d[u] > BLOCK) {
int ans = 0;
io.write(B[u].qry(), '\n');
} else {
B[u].clear();
for (vi::iterator it = G[u].begin(); it != G[u].end(); it++) {
B[u].update(a[*it], 1);
}
io.write(B[u].qry(), '\n');
}
}
}
分块的数据结构 B 请自行脑补。