#include "werewolf.h"
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <vector>
//#include "werewolf.h"
using namespace std;
vector<int>adj[200005];
int ord[2000005],timp=0;
int poz[200005];
int maxim[800005];
int minim[800005];
void dfs(int curr,int par)
{
ord[timp+1]=curr;
poz[curr]=timp+1;
timp++;
for(auto k:adj[curr])
{
if(k!=par)
{
dfs(k,curr);
}
}
}
void build(int node,int st,int dr)
{
if(st==dr)
{
maxim[node]=ord[st];
minim[node]=ord[st];
return;
}
int mij=(st+dr)/2;
build(node*2,st,mij);
build(node*2+1,mij+1,dr);
maxim[node]=max(maxim[node*2],maxim[node*2+1]);
minim[node]=min(minim[node*2],minim[node*2+1]);
}
int best;
void findfirst(int node,int st,int dr,int qst,int qdr,int lower,int upper)
{
if(st>qdr || st>dr || qst>dr || qst>qdr)
{
return;
}
int mij=(st+dr)/2;
if(qst<=st && dr<=qdr)
{
if(maxim[node]<lower || minim[node]>upper)
{
return;
}
if(st==dr)
{
best=min(best,st);
return;
}
else
{
if(maxim[node*2]<lower || minim[node*2]>upper)
{
findfirst(node*2+1,mij+1,dr,qst,qdr,lower,upper);
}
else
{
findfirst(node*2,st,mij,qst,qdr,lower,upper);
}
}
return;
}
findfirst(node*2,st,mij,qst,qdr,lower,upper);
findfirst(node*2+1,mij+1,dr,qst,qdr,lower,upper);
}
int best2;
void findlast(int node,int st,int dr,int qst,int qdr,int lower,int upper)
{
if(st>qdr || st>dr || qst>dr || qst>qdr)
{
return;
}
int mij=(st+dr)/2;
if(qst<=st && dr<=qdr)
{
if(maxim[node]<lower || minim[node]>upper)
{
return;
}
if(st==dr)
{
best2=max(best2,st);
return;
}
else
{
if(maxim[node*2+1]<lower || minim[node*2+1]>upper)
{
findlast(node*2,st,mij,qst,qdr,lower,upper);
}
else
{
findlast(node*2+1,mij+1,dr,qst,qdr,lower,upper);
}
}
return;
}
findlast(node*2,st,mij,qst,qdr,lower,upper);
findlast(node*2+1,mij+1,dr,qst,qdr,lower,upper);
}
std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,
std::vector<int> S, std::vector<int> E,
std::vector<int> L, std::vector<int> R) {
int n=N,dim;
int m=X.size();
int q=S.size();
vector<int>rasp;
int root=0;
for(int i=0;i<m;i++)
{
adj[X[i]].push_back(Y[i]);
adj[Y[i]].push_back(X[i]);
}
for(int i=0;i<m;i++)
{
if(adj[i].size()==1)
{
root=i;
}
}
dfs(root,-1);
build(1,1,n);
for(int i=0;i<q;i++)
{
int rez;
best=n+1;
best2=-1;
if(poz[S[i]]<poz[E[i]])
{
findlast(1,1,n,poz[S[i]],poz[E[i]],R[i]+1,n-1);
findfirst(1,1,n,poz[S[i]],poz[E[i]],0,L[i]-1);
if(best==n+1 || best2==-1)
{
rez=1;
}
else if(best2+1<best)
{
rez=1;
}
else
{
rez=0;
}
rasp.push_back(rez);
}
else
{
findlast(1,1,n,poz[S[i]],poz[E[i]],0,L[i]-1);
findfirst(1,1,n,poz[S[i]],poz[E[i]],R[i]+1,n-1);
if(best==n+1 || best2==-1)
{
rez=1;
}
else if(best2+1<best)
{
rez=1;
}
else
{
rez=0;
}
rasp.push_back(rez);
}
}
return rasp;
}
