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;
}