2297: 蓝桥杯2018年第九届真题-版本分支 (时间复杂度O(M+Q))

解题思路:

注意事项:

参考代码:

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#define F(i,j,k) for(int i = j; i < k; ++i)
#define R(i,j,k) for(int i = j; i >= k; --i)
#define ct cout<<
#define kg <<' '<<
#define ed <<endl
#define ve vector
#define N 100005
#define p1 p.first
#define p2 p.second
using namespace std;
int n,m,x,y;
ve<int> d[N];ve<pair<int ,int>>q[N];
bool ans[N],vis[N];
void check(int node){
    for(auto &p : q[node]){
        if(vis[p1]){
            ans[p2] = 1;
        }
    }
}
 
void dfs(int node){
    vis[node] = 1;
    check(node);
    for(int &i : d[node]){
        dfs(i);
    }
    vis[node] = 0;
}
 
int main(){ios::sync_with_stdio(0),cin.tie(0);
    cin>>n>>m;
    F(i,1,n){
        cin>>x>>y;
        d[x].push_back(y);
    }
    F(i,0,m){
        cin>>x>>y;
        q[y].push_back({x,i});
    }
    dfs(1);
    F(i,0,m){
        if(ans[i])printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}