C11BC2 - Robin

Tác giả: skyvn97

Ngôn ngữ: C++

#include<cstdio>
#include<vector>
#define MAX   10101
#define LOG   14
#define FOR(i,a,b) for (int i=(a),_b=(b);i<=_b;i=i+1)
#define FORD(i,b,a) for (int i=(b),_a=(a);i>=_a;i=i-1)
#define REP(i,n) for (int i=0,_n=(n);i<_n;i=i+1)
#define fi   first
#define se   second
using namespace std;
vector<pair<int,int> > adj[MAX];
int h[MAX];
int par[MAX][LOG+1];
bool haveEdge[MAX][LOG+1];
int n,q;
void loadtree(void) {
    scanf("%d%d",&n,&q);
    FOR(i,2,n) {
        int j,t;
        scanf("%d%d",&j,&t);
        adj[i].push_back(make_pair(j,t));
        adj[j].push_back(make_pair(i,t));
    }
    h[0]=-1;
}
void dfs(int u) {
    REP(i,adj[u].size()) if (adj[u][i].fi!=par[u][0]) {
        int v=adj[u][i].fi;
        h[v]=h[u]+1;
        par[v][0]=u;
        haveEdge[v][0]=adj[u][i].se==2;
        dfs(v);
    }
}
void setupLCA(void) {
    dfs(1);
    FOR(j,1,LOG) FOR(i,1,n) {
        par[i][j]=par[par[i][j-1]][j-1];
        haveEdge[i][j]=haveEdge[i][j-1]||haveEdge[par[i][j-1]][j-1];
    }
}
bool answer(int u,int v) {
    if (h[u]<h[v]) return (answer(v,u));
    FORD(i,LOG,0) if (h[par[u][i]]>=h[v]) {
        if (haveEdge[u][i]) return (true);
        u=par[u][i];
    }
    if (u==v) return (false);
    FORD(i,LOG,0) if (par[u][i]!=par[v][i]) {
        if (haveEdge[u][i]) return (true);
        if (haveEdge[v][i]) return (true);
        u=par[u][i];
        v=par[v][i];
    }
    return (haveEdge[u][0]||haveEdge[v][0]);
}
void process(void) {
    REP(zz,q) {
        int u,v;
        scanf("%d%d",&u,&v);
        printf("%s\n",answer(u,v)?"YES":"NO");
    }
}
int main(void) {
    loadtree();
    setupLCA();
    process();
    return 0;
}

Download