题意：有三种操作：
1.新增一条边从y连向x，此前x没有父节点
2.x接到一份文件，（文件标号逐次递增），然后将这份文件一路上溯，让所有上溯的节点都接到这份文件
3.查询某个节点x是否接到过文件F
解法：
首先要知道一个性质，节点u在v的上溯路径上的话要满足： L[u]<=L[v] && R[u] >= R[v] （先进后出）
先将所有的边都读入，dfs得出L[u],R[u]，然后将查询分为tot类（tot=总文件种数），记录每一类有那些地方查询了，然后如果type=2,那么记录这个type=2现在是第几类文件，都存下来以后备用。
再从1枚举到m，枚举每个输入，
如果type=1，那么将x,y集合合并，就算是建立了父子关系。
如果type=2，那么先得出现在得到的文件种类，再得到这个种类的所有查询，处理所有查询，得到u,v，先判断是否在一个集合中，然后再进行L[u]<=L[v] && R[u] >= R[v] 的判断，如果成立，说明u接到了v传来的该种类的文件。
如果type=3，先不处理，但是按照题意，也可以直接输出了。
最后输出。
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
#define N 100107 vector<int> G[N],query[N];
int fa[N],L[N],R[N],vis[N],Time,doc[N],f[N];
struct node{
int op,x,y;
}Q[N]; int findset(int x) {
if(x != fa[x]) fa[x] = findset(fa[x]);
return fa[x];
} void dfs(int u) {
vis[u] = ;
L[u] = ++Time;
for(int i=;i<G[u].size();i++) {
int v = G[u][i];
dfs(v);
}
R[u] = ++Time;
} int main()
{
int n,m,i,op,DOC = ,docnum;
memset(vis,,sizeof(vis));
scanf("%d%d",&n,&m);
for(i=;i<=n;i++) fa[i] = i;
for(i=;i<=m;i++) {
scanf("%d",&Q[i].op);
if(Q[i].op == ) {
scanf("%d%d",&Q[i].x,&Q[i].y);
G[Q[i].y].push_back(Q[i].x);
vis[Q[i].x] = ;
}
else if(Q[i].op == ) {
scanf("%d",&Q[i].x);
doc[i] = ++DOC; //第i个查询是查询第DOC种文档
}
else {
scanf("%d%d",&Q[i].x,&docnum);
query[docnum].push_back(i); //查询第docnum种文档的查询标号
}
}
Time = ;
memset(f,,sizeof(f));
for(i=;i<=n;i++)
if(!vis[i]) dfs(i); //处理出L[u],R[u]
for(i=;i<=m;i++) {
if(Q[i].op == ) {
int fx = findset(Q[i].x);
int fy = findset(Q[i].y);
fa[fx] = fy;
}
else if(Q[i].op == ) {
int now = doc[i]; //是第几种文档
int v = Q[i].x; //最底层签发者
for(int j=;j<query[now].size();j++) {
int ind = query[now][j];
int u = Q[ind].x; //查询目标
if(findset(u) == findset(v) && L[u] <= L[v] && R[u] >= R[v])
f[ind] = ;
}
}
}
for(i=;i<=m;i++) if(Q[i].op == ) {
if(f[i]) puts("YES");
else puts("NO");
}
return ;
}