F - Well-defined Path Queries on a Namori

• Time : O(v + e + elogv + qlogv)
• Space : O(v + e)

c++

#include <bits/stdc++.h>

#pragma optimization_level 3
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#pragma GCC optimize("Ofast")//Comment optimisations for interactive problems (use endl)
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")

using namespace std;

struct PairHash {inline std::size_t operator()(const std::pair<int, int> &v) const { return v.first * 31 + v.second; }};

// speed
#define Code ios_base::sync_with_stdio(false);
#define By ios::sync_with_stdio(0);
#define Sumfi cout.tie(NULL);

// alias
using ll = long long;
using ld = long double;
using ull = unsigned long long;

// constants
const ld PI = 3.14159265358979323846;  /* pi */
const ll INF = 1e18;
const ld EPS = 1e-9;
const ll MAX_N = 202020;
const ll mod = 1e9 + 7;

// typedef
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef array<ll,3> all3;
typedef array<ll,5> all5;
typedef vector<all3> vall3;
typedef vector<all5> vall5;
typedef vector<ld> vld;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<int> vi;
typedef pair<string, string> pss;
typedef vector<pss> vpss;
typedef vector<string> vs;
typedef vector<vs> vvs;
typedef unordered_set<ll> usll;
typedef unordered_set<pll, PairHash> uspll;
typedef unordered_map<ll, ll> umll;
typedef unordered_map<pll, ll, PairHash> umpll;

// macros
#define rep(i,m,n) for(ll i=m;i<n;i++)
#define rrep(i,m,n) for(ll i=n;i>=m;i--)
#define all(a) begin(a), end(a)
#define rall(a) rbegin(a), rend(a)
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
#define ASCEND(a) iota(all(a),0)
#define sz(x) ll((x).size())
#define pyes cout<<"Yes\n";
#define pno cout<<"No\n";
#define pneg1 cout<<"-1\n";
#define ppossible cout<<"Possible\n";
#define pimpossible cout<<"Impossible\n";
#define CASE(x) cout<<"Case #"<<x<<": ";

// utility functions
template <typename T>
void print(T &&t)  { cout << t << "\n"; }
template<typename T>
void printv(vector<T>v){ll n=v.size();rep(i,0,n)cout<<v[i]<<" ";cout<<"\n";}
void fileIO() {freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);}
void hackerCupIO() {freopen("/Users/summerflower/Downloads/second_flight_input.txt", "r", stdin); freopen("/Users/summerflower/Downloads/solution.txt","w",stdout);}
//void readf() {freopen("", "rt", stdin);}
template<typename T>
void readv(vector<T>& v){rep(i,0,sz(v)) cin>>v[i];}
void readpll(pll& A) {cin>>A.first>>A.second;}
void readvpll(vpll& A) {rep(i,0,sz(A)) readpll(A[i]); }
void readvall3(vall3& A) {rep(i,0,sz(A)) cin>>A[i][0]>>A[i][1]>>A[i][2];}
void readvvll(vvll& A) {rep(i,0,sz(A)) readv(A[i]);}

// geometry data structures
template <typename T>
struct Point {
    T y,x;
    Point() {}
    void input() {cin>>y>>x;}
};

template<typename T>
struct Circle {
    Point<T> center;
    T radius;
    Circle() {}

    void input() {
        center = Point<T>();
        center.input();
        cin>>radius;
    }

    bool circumference(Point<T> p) {
        return (center.x - p.x) * (center.x - p.x) + (center.y - p.y) * (center.y - p.y) == radius * radius;
    }

    bool intersect(Circle<T> c) {
        T d = (center.x - c.center.x) * (center.x - c.center.x) + (center.y - c.center.y) * (center.y - c.center.y);
        return (radius - c.radius) * (radius - c.radius) <= d and d <= (radius + c.radius) * (radius + c.radius);
    }
};

ll __gcd(ll x, ll y) { return !y ? x : __gcd(y, x % y); }
ll __lcm(ll x, ll y) { return x / __gcd(x,y) * y; }
ll modpow(ll n, ll x, ll MOD = mod) { if(!x) return 1; ll res = modpow(n,x>>1,MOD); res = (res * res) % MOD; if(x&1) res = (res * n) % MOD; return res; }


ll uf[MAX_N];
ll find(ll u) {
    return uf[u] == u ? u : uf[u] = find(uf[u]);
}
void uni(ll u, ll v) {
    ll pu = find(u), pv = find(v);
    uf[pu] = uf[pv] = min(pu,pv);
}

vll adj[MAX_N];
vector<vvll> bccs;
vvll st;
ll id = 1, vis[MAX_N], mi[MAX_N];

void dfs(ll u, ll par) {
    mi[u] = vis[u] = id++;
    for(auto& v : adj[u]) {
        if(v == par) continue;
        if(vis[u] > vis[v]) st.push_back({u,v});

        if(vis[v]) mi[u] = min(mi[u], vis[v]);
        else {
            dfs(v,u);
            mi[u] = min(mi[u],mi[v]);
            if(mi[v] >= vis[u]) {
                bccs.emplace_back();
                while(!st.empty()) {
                    auto e = st.back(); st.pop_back();
                    bccs.back().push_back(e);
                    if(e[0] == u and e[1] == v) break;
                }
            }
        }
    }
}

vector<bool> solve(vpll& A, vpll& Q) {
    ASCEND(uf);
    rep(i,0,sz(A)) {
        auto [u,v] = A[i];
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    rep(i,0,sz(A)) {
        if(!vis[i+1])
            dfs(i+1,-1);
    }

    rep(i,0,sz(bccs)) {
        if(sz(bccs[i]) != 1) continue;
        uni(bccs[i][0][0], bccs[i][0][1]);
    }

    vector<bool> res;
    rep(i,0,sz(Q)) {
        auto [u,v] = Q[i];
        res.push_back(find(u) == find(v));
    }

    return res;
}

int main() {
    Code By Sumfi
    cout.precision(12);
    ll tc = 1;
    //cin>>tc;
    rep(i,1,tc+1) {
        ll n,q;
        cin>>n;
        vpll A(n);
        readvpll(A);
        cin>>q;
        vpll Q(q);
        readvpll(Q);
        for(auto r : solve(A,Q)) if(r) pyes else pno
    }
    return 0;
}