ABC 266F
  • 板块学术版
  • 楼主d0j1a_1701
  • 当前回复2
  • 已保存回复2
  • 发布时间2022/10/5 00:49
  • 上次更新2023/10/27 08:45:45
查看原帖
ABC 266F
248302
d0j1a_1701楼主2022/10/5 00:49

rt 思路类似倍增LCA,求出u,v的简单路径上是否经过环边

#include <algorithm>
#include <iostream>
#include <cstring>
#include <list>
using namespace std;
struct IO{
#ifdef FIO
	const static int BUFSIZE=1<<20;char buf[BUFSIZE],obuf[BUFSIZE],*p1,*p2,*pp;inline char gc(){return(p1==p2&&(p2=(p1=buf)+fread(buf,1,BUFSIZE,stdin),p1==p2)?EOF:*p1++);}inline void pc(char x){((pp-obuf==BUFSIZE&&(fwrite(obuf,1,BUFSIZE,stdout),pp=obuf)),*pp=x,pp++);}inline void flush(){fwrite(obuf,1,pp-obuf,stdout);}IO(){p1=buf,p2=buf,pp=obuf;}~IO(){fwrite(obuf,1,pp-obuf,stdout);}
#else
	int(*gc)()=&getchar;int(*pc)(int)=&putchar;inline void flush(){};
#endif
	template<typename Tp>inline int read(Tp&s){int f=1;char ch=gc();s=0;while(!isdigit(ch)&&ch!=EOF)f=(ch=='-'?-1:1),ch=gc();while(isdigit(ch))s=s*10+(ch^48),ch=gc();s*=f;return ch!=EOF;}template<typename Tp=int>inline Tp read(){Tp x;read(x);return x;}template<typename Tp,typename...Ts>int read(Tp&x,Ts&...val){return read(x)&&read(val...);}template<typename Tp>void write(Tp x){if(x<0)pc('-'),x=-x;static char sta[20];int top=0;do sta[top++]=x%10+'0',x/=10;while(x);while(top)pc(sta[--top]);}template<typename Tp,typename...Ts>void write(Tp x,Ts...val){write(x);pc(' ');write(val...);}template<typename...Ts>void writeln(Ts...val){write(val...);pc('\n');}}io;
int n,q,x,y,fa[200010][30],lg[200010],dep[200010];
bool vis[200010],mark[200010][30];
list<int> edges[200010];
void dfs1(int u,int fa){
	vis[u] = true;
	for(int v:edges[u]){
		if(v==fa)	continue;
		if(vis[v])	x = u,y = v;
		else dfs1(v,u);
		if(x)	return;
	}
}
void dfs2(int u){
	for(int v:edges[u])
		if(v!=fa[u][0]&&!(u==x&&v==y||u==y&&v==x))
			fa[v][0] = u,dep[v] = dep[u] + 1,dfs2(v);
}
inline int lca(int u,int v){
	if(dep[u]<dep[v])	swap(u,v);
	for(int i = lg[n]; i >= 0; i--)
		if(dep[fa[u][i]] >= dep[v])
			u = fa[u][i];
	if(u == v)    return u;
	for(int i = lg[n]; i >= 0; i--)
		if(fa[u][i] != fa[v][i])
			u = fa[u][i], v = fa[v][i];
	return fa[u][0];
}
inline void init(int s){
	dfs1(s,0),dfs2(s),fa[s][0] = s;
	for(int j=1;j<=lg[n];j++)
		for(int i=1;i<=n;i++)
			fa[i][j] = fa[fa[i][j-1]][j-1];
	int l = lca(x,y),p = x;
	while(p!=l)	mark[p][0] = true,p = fa[p][0];
	p = y;while(p!=l)	mark[p][0] = true,p = fa[p][0];
	for(int j=1;j<=lg[n];j++)
		for(int i=1;i<=n;i++)
			mark[i][j] |= (mark[i][j-1] | mark[fa[i][j-1]][j-1]);
}
inline bool solve(int u,int v){
	bool res = false;
	if(dep[u]<dep[v])	swap(u,v);
	for(int i = lg[n]; i >= 0; i--)
		if(dep[fa[u][i]] >= dep[v])
			res |= mark[u][i], u = fa[u][i];
	if(u == v)    return res;
	for(int i = lg[n]; i >= 0; i--)
		if(fa[u][i] != fa[v][i])
			res |= mark[u][i] | mark[v][i], u = fa[u][i], v = fa[v][i];
	return res | mark[u][0];
}
int main(){
	io.read(n);
	for(int i=2;i<=n;i++)	lg[i] = lg[i >> 1] + 1;
	for(int i=1;i<=n;i++){
		int u,v;io.read(u,v);
		edges[u].push_back(v);
		edges[v].push_back(u);
	}
	init(1);
	io.read(q);
	for(int i=1;i<=q;i++){
		int u,v;io.read(u,v);
		printf(solve(u,v)?"No\n":"Yes\n");
	}
	return 0;
}
/*
  9
  1 2
  2 3
  3 4
  1 4
  1 5
  1 6
  4 7
  3 8
  2 9
 */
2022/10/5 00:49
加载中...