\(\text{Solution}\)

一个人能否拿到文件取决于这个人在不在文件初始拥有者与其根的链上。那我们用冰茶姬维护员工的根，出现文件时将此时的那条链记录下来，最后跑一遍树确定在不在链上即可。（注意题目中有每个员工的上司不会改变的条件，我们的树只会增边不会改边，所以跑最后连出来的树而不用记录过程的树）

最后一个小思考：如果这道题变成给定一棵树怎么做（相当于只有 \(2,3\) 操作）。我们把文件相同的询问和插入放在一起，然后树链剖分将那一条链置为 \(1\)，然后查询节点权值是否为 \(1\)，然后再置为 \(0\)（感觉有点麻烦但蒟蒻只能想到这个做法）。

\(\text{Code}\)

#include <cstdio>
#include <vector>
using namespace std;

const int N=1e5+5;

int n,m,f[N],s[N],t[N],ans[N],tot,cnt;
vector <int> e[N];
vector <pair<int,int> > vec[N];
bool vis[N];

int read() {
	int x=0,f=1; char s;
	while((s=getchar())>‘9‘||s<‘0‘) if(s==‘-‘) f=-1;
	while(s>=‘0‘&&s<=‘9‘) x=(x<<1)+(x<<3)+(s^48),s=getchar();
	return x*f;
}

void init() {for(int i=1;i<=n;++i) f[i]=i;}

int Find(int x) {return x==f[x]?x:f[x]=Find(f[x]);}

void dfs(int u) {
	vis[u]=1;
	for(int i=0;i<e[u].size();++i) dfs(e[u][i]);
	for(int i=0;i<vec[u].size();++i) if(vis[vec[u][i].first]) ++ans[vec[u][i].second];
	vis[u]=0;
}

int main() {
	n=read(),m=read();
	init();
	int op,x,y;
	for(int i=1;i<=m;++i) {
		op=read(),x=read();
		if(op==1) {
			y=read();
			e[y].push_back(x); f[x]=y;
		}
		else if(op==2) {
			++tot; s[tot]=x,t[tot]=Find(x);
		}
		else {
			y=read(); ++cnt;
			vec[s[y]].push_back(make_pair(x,cnt));
			vec[x].push_back(make_pair(t[y],cnt));
		}
	}
	for(int i=1;i<=n;++i) if(f[i]==i) dfs(i);
	for(int i=1;i<=cnt;++i) puts(ans[i]==2?"YES":"NO");
	return 0;
}

CodeForces - 466E Information Graph

原文：https://www.cnblogs.com/AWhiteWall/p/13525031.html