#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
typedef pair<ll,ll> pii;
const ll MAXN = 2e5+5;
const ll INF = 1e9+7;
vector<vector<ll>>adj(MAXN);
ll arr[MAXN],position[MAXN],seg[4*MAXN][2];
//seg[i][0]=min
//vector<vector<ll>>seg(4*MAXN);
void recalculate(ll node){
//seg[node].resize(0);
seg[node][0]=min(seg[2*node+1][0],seg[2*node+2][0]);
seg[node][1]=max(seg[2*node+1][1],seg[2*node+2][1]);
}
void build(ll node, ll left, ll right){
if(left==right){
seg[node][0]=arr[left];
seg[node][1]=arr[left];
}else{
ll middle=(left+right)/2;
build(2*node+1,left,middle);
build(2*node+2,middle+1,right);
recalculate(node);
}
}
ll querie(ll node, ll left, ll right, ll a, ll b, ll type){
if(a<=left&&b>=right){
return seg[node][type];
}else{
ll middle=(left+right)/2,res=0;
if(type==1){
if(a<=middle)res=max(res,querie(2*node+1,left,middle,a,b,type));
if(b>=middle+1)res=max(res,querie(2*node+2,middle+1,right,a,b,type));
}else{res=INF;
if(a<=middle)res=min(res,querie(2*node+1,left,middle,a,b,type));
if(b>=middle+1)res=min(res,querie(2*node+2,middle+1,right,a,b,type));
}
return res;
}
}
void dfs(ll node, ll p,ll pos){
arr[pos]=node;
position[node]=pos;
for(auto u:adj[node]){
if(u==p)continue;
dfs(u,node,pos+1);
}
}
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 Q = S.size(),m=(int)X.size(), i,n=N,m1,m2;
for(i=0;i<m;i++){
adj[X[i]].pb(Y[i]);
adj[Y[i]].pb(X[i]);
}
for(i=0;i<N;i++){
if(adj[i].size()==1)break;
}
dfs(i,-1,1);
build(0,1,n);
int s,e,l,r; ll lo,hi,mid;
std::vector<int> A(Q);
for(i=0;i<Q;i++){//cout<<i<<"\n";
s=S[i]; e=E[i]; l=L[i]; r=R[i];
if(s<l||e>r){
A[i]=0;
continue;
}
// cout<<position[s]<<" "<<position[e]<<endl;
if(position[s]<position[e]){//cout<<"hihi";
//saber qual a leftmost pos com arr[pos] < l
hi=position[e];lo=position[s];
if( querie(0,1,n,lo,hi,0)>=l ){//cout<<"kk ";
A[i]=1;
continue;
}
while(hi-lo>=2){
mid = lo + (hi-lo)/2;
if( querie(0,1,n,lo,mid,0)>=l ){
lo=mid;
}else{
hi=mid;
}
}
for(mid=lo;mid<=hi;mid++){
if( querie(0,1,n,mid,mid,0)<l ){
break;
}
}
m1=mid-1;
//human so pode andar entre position[e] e mid-1
//saber qual a rightmost pos com arr[pos] > r
hi=position[e];lo=position[s];
if( querie(0,1,n,lo,hi,1)<=r ){//cout<<"gaga";
A[i]=1;
continue;
}
while(hi-lo>=2){
mid = lo + (hi-lo)/2;
if( querie(0,1,n,mid,hi,1)<=r ){
hi=mid;
}else{
lo=mid;
}
}
for(mid=hi;mid>=lo;mid--){
if( querie(0,1,n,mid,mid,1)>r ){
break;
}
}
m2=mid+1;
A[i]=0;
if(m1>=m2){
A[i]=1;
}
//cout<<m1<<" "<<m2<<endl;
}else{
//saber qual a leftmost pos com arr[pos] > r
lo=position[e]; hi=position[s];
if( querie(0,1,n,lo,hi,1)<=r ){
A[i]=1;
continue;
}
while(hi-lo>=2){
mid = lo + (hi-lo)/2;
if( querie(0,1,n,lo,mid,1)<=r ){
lo=mid;
}else{
hi=mid;
}
}
for(mid=lo;mid<=hi;mid++){
if( querie(0,1,n,mid,mid,1)>r ){
break;
}
}
m1=mid-1;
//human so pode andar entre position[e] e mid-1
//saber qual a rightmost pos com arr[pos] <l
hi=position[s];lo=position[e];
if( querie(0,1,n,lo,hi,0)>=l ){
A[i]=1;
continue;
}
while(hi-lo>=2){
mid = lo + (hi-lo)/2;
if( querie(0,1,n,mid,hi,0)>=l ){
hi=mid;
}else{
lo=mid;
}
}
for(mid=hi;mid>=lo;mid--){
if( querie(0,1,n,mid,mid,0)<l ){
break;
}
}
m2=mid+1;
//human so pode andar entre position[e] e mid-1
A[i]=0;
if(m1>=m2){
A[i]=1;
}
}
}
return A;
}
