题解：CF466E Information Graph

模拟赛把 T1 跳了来写这个（T3），离线思路很简单，比 T1 思维题好想。

首先，最终状态是若干颗上下级关系的树，所以我们可以将整个问题放在最后建好的树树上考虑。

对于操作一，将

x

与

y

连边即可。

对于操作二，可以用并查集优化复杂度快速找出当前的最高上司。

对于操作三，我们在每次操作二时把上下两个节点

(u_p, u_d)

储存下来，判断节点

x

是否在路径

i

上可以使用最近公共祖先（LCA），若

\text{LCA}(u_p, x) = u_p \land \text{LCA}(x, u_d) = x

，则

x

在路径上，反之则不在。

需要注意的是，最终状态不一定是一棵树，可能有多棵树，在 LCA 初始化时要处理一下。

倍增写 LCA 的话时间复杂度为

O(n \log n)

。

赛时代码如下：

CPP

namespace dsu {
	int fa[N];
	void init(int n) {
		for(int i = 1; i <= n; i++) fa[i] = i;
	}
	int find(int u) {
		if(fa[u] == u) return u;
		fa[u] = find(fa[u]);
		return fa[u];
	}
	void connect(int u, int v) {
		fa[u] = v;
	}
}
typedef pair<int, int> pii;
 
vector <int> G[N]; // 存图
int n, m;
vector <pii> ask; // 离线询问
pii cov[N]; // 操作二区间存储
int tp = 0;
int root;
int st[N][20];
int dep[N];
bool vis[N];
 
void dfs(int u, int f, int d) {
	vis[u] = 1;
	st[u][0] = f;
	dep[u] = d;
	for(int i = 1; i <= 19; i++) st[u][i] = st[ st[u][i - 1] ][i - 1];
	for(auto v : G[u]) {
		if(v == f) continue;
		dfs(v, u, d + 1);
	}
	return;
}
int lca(int u, int v) {
	if(dep[u] < dep[v]) swap(u, v);
	if(u == v) return u;
	for(int i = 19; i >= 0; i--) {
		if(dep[st[u][i]] >= dep[v]) u = st[u][i];
	}
	if(u == v) return u;
	for(int i = 19; i >= 0; i--) {
		if(st[u][i] != st[v][i]) u = st[u][i], v = st[v][i];
	}
	return st[u][0];
}
vector <int> rootl;
 
int32_t main() {
	n = read(), m = read();
	dsu::init(n);
	while(m--) {
		int opt = read();
		if(opt == -1) break;
		if(opt == 1) {
			int u = read(), v = read();
			dsu::connect(u, v);
			G[u].push_back(v);
			G[v].push_back(u);
			rootl.push_back(v);		
		} else if(opt == 2) {
			int u = read();
			cov[++tp] = {u, dsu::find(u)};
			//cout << "Line: " << tp <<" / "<< u << " -> " << dsu::find(u) << endl;
		} else {
			int u = read(), v = read();
			ask.push_back({u, v});
		}
	}
	for(int i = 1; i <= n; i++) {
		int root = dsu::find(i);
		if(!vis[root]) 	dfs(root, root, 1);
	}//不止一棵树，有多个根节点要初始化 
	for(auto [x, i]:ask) {
		int upp = cov[i].second, udd = cov[i].first;
		if(dsu::find(x) != dsu::find(upp)) cout << "NO" << endl;
		else if(x == upp || x == udd) cout << "YES" << endl;	
		else cout << (lca(upp, x) == upp && lca(udd, x) == x ? "YES" : "NO") << endl;
	}
	return 0;
}

题解：CF466E Information Graph

文章操作

相关推荐

评论

题解：CF466E Information Graph