蒟蒻求调
查看原帖
蒟蒻求调
461359
huangrenheluogu楼主2023/11/20 18:56
#include<bits/stdc++.h>
using namespace std;
const int N = 2e4 + 5, M = 1e5 + 5;
int n, m, q, fir[N], nxt[M << 1], son[M << 1], tot, u, v, dfsn[N], low[N], cnt, s[N], t, to[N], w, Fir[N], Nxt[N << 1], Son[N << 1], fa[N][16], dep[N], f[N];
bool cut[N], ans;
inline void add(int x, int y){
	nxt[++tot] = fir[x];
	fir[x] = tot;
	son[tot] = y;
}
inline void Add(int x, int y){
	Nxt[++tot] = Fir[x];
	Fir[x] = tot;
	Son[tot] = y;
}
inline void dfs(int x, int ff){
	low[x] = dfsn[x] = ++tot;
	s[++t] = x;
	int S = 0;
	for(int i = fir[x]; i ; i = nxt[i]){
		if(son[i] == ff) continue ;
		if(dfsn[son[i]]) low[x] = min(low[x], dfsn[son[i]]);
		else{
			S++;
			dfs(son[i], x);
			low[x] = min(low[x], low[son[i]]);
			if(low[son[i]] >= dfsn[x]){
				cnt++;
				cut[x] = 1;
				while(s[t + 1] != son[i]){
					to[s[t--]] = cnt;
				}
			}
		}
	}
	if(x == 1 && S == 1){
		cut[1] = 0;
		to[1] = cnt;
	}
}
inline void dfs2(int x, int ff){
	dep[x] = dep[ff] + 1;
	fa[x][0] = ff;
	for(int i = 1; i <= 15; i++) fa[x][i] = fa[fa[x][i - 1]][i - 1];
	for(int i = Fir[x]; i ; i = Nxt[i]){
		if(Son[i] == ff) continue ;
		dfs2(Son[i], x);
	}
}
inline int lca(int x, int y){
	if(dep[x] > dep[y]) swap(x, y);
	for(int i = 15; ~i; i--){
		if(dep[fa[y][i]] >= dep[x]) y = fa[y][i];
	}
	if(x == y) return x;
	for(int i = 15; ~i; i--){
		if(fa[y][i] != fa[x][i]){
			y = fa[y][i], x = fa[x][i];
		}
	}
	return fa[x][0];
}
inline int dis(int x, int y){
	return dep[x] + dep[y] - 2 * dep[lca(x, y)];
}
inline int getfa(int x){
	return f[x] == x ? x : f[x] = getfa(f[x]);
}
int main(){
//	freopen("data.in", "r", stdin);
//	freopen("code.out", "w", stdout);
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= m; i++){
		scanf("%d%d", &u, &v);
		add(u, v), add(v, u);
	}
	tot = 0;
	dfs(1, 0);
	for(int i = 1; i <= n; i++) if(cut[i]) to[i] = ++cnt;
	for(int i = 1; i <= cnt; i++) f[i] = i;
	tot = 0;
	for(int i = 1; i <= n; i++){
		for(int j = fir[i]; j ; j = nxt[j]){
			if(to[son[j]] != to[i]){
				if(getfa(to[i]) != getfa(to[son[j]])){
					Add(to[i], to[son[j]]);
					Add(to[son[j]], to[i]);
					f[getfa(to[i])] = getfa(to[son[j]]);
				}
			}
		}
	}
	dfs2(1, 0);
	scanf("%d", &q);
	while(q--){
		scanf("%d%d%d", &u, &v, &w);
		ans = 1;
		if(to[u] == to[v]) ans = 0;
		if(dis(to[u], to[v]) != dis(to[u], to[w]) + dis(to[v], to[w])) ans = 0;
		if(!cut[w]) ans = 0;
		if(w == u || w == v) ans = 1;
		printf(ans ? "yes\n" : "no\n");
	}
	return 0;
}

2023/11/20 18:56
加载中...