[Hackerearth] Cryptic Line

 

Problem Link    : Cryptic Line
Category        : Graph Theory
Contest         : January Easy '24

#include "bits/stdc++.h"
using namespace std;
#define int     long long int
#define endl    '\n'
 
int n;
int q;
vector<vector<int>> graph;
vector<int> in;
vector<int> out;
int dfsTime;
 
void dfs(int u, int p) {
    in[u] = ++dfsTime;
    for (int v : graph[u]) {
        if (v == p) {
            continue;
        }
        dfs(v, u);
    }
    out[u] = dfsTime;
}
 
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cout.precision(12);
 
    bool FILEIO = 1;
    if (FILEIO and fopen("in.txt", "r")) {
        freopen("in.txt", "r", stdin);
    }
 
    cin >> n >> q;
    graph.resize(n + 1);
    in.resize(n + 1);
    out.resize(n + 1);
    for (int e = 1; e < n; e++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    dfs(1, 0);
    while (q--) {
        int x, y;
        cin >> x >> y;
        if (in[x] < in[y] and out[x] >= out[y]) {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }
    }
}