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
*/