这个人只会做这种水题了。。。
Solution
直接做显然不太好做，考虑把询问离线下来在静态森林中查询。
对于操作 1，直接连边就可以了。
对于操作 2，容易发现能看到这个文件的一定是一条从祖先到子节点的一条链，记录这个文件被看到的链顶和链底即可。
对于操作 3，只需要知道 \(x\) 在不在某条链上。显然可以大力树剖，不过这里有更简单的方法。
利用这条链是祖先向下的性质，\(x\) 在这条链上的充要条件是 \(x\) 在链顶的子树中，链底在 \(x\) 的子树中。
判断是否在子树中直接欧拉序就好了。
#include <bits/stdc++.h>
#define rep(i, j, k) for(int i = (j); i <= (k); i ++)
#define per(i, j, k) for(int i = (j); i >= (k); i --)
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int N = 1e5 + 5, INF = 0x3f3f3f3f;
const LL mod = 1e9 + 7;
int n, m, idx;
vector<int> e[N];
int st[N], ed[N];
int fa[N];
int L[N], R[N], tim;
vector<array<int, 3>> event;
int find(int x) {
return fa[x] == x ? x : fa[x] = find(fa[x]);
}
void dfs(int u) {
L[u] = ++ tim;
for(auto v : e[u]) dfs(v);
R[u] = tim;
}
bool ins(int u, int v) { // v 是否在 u子树里
return L[u] <= L[v] && L[v] <= R[u];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> n >> m;
rep(i, 1, n) fa[i] = i;
while(m --) {
int op, u, v;
cin >> op >> u;
if(op == 1) {
cin >> v;
e[v].push_back(u);
fa[u] = find(v);
}
else if(op == 2) {
st[++ idx] = find(u);
ed[idx] = u;
}
else {
cin >> v;
event.push_back({st[v], ed[v], u});
}
}
rep(i, 1, n) if(find(i) == i) dfs(i);
for(auto evt : event) {
if(ins(evt[0], evt[2]) && ins(evt[2], evt[1])) cout << "YES\n";
else cout << "NO\n";
}
return 0;
}