#include "werewolf.h"
//#include "grader.cpp"
#include <vector>
#include <assert.h>
#include <iostream>
#include <functional>
using namespace std;
const int MAXN = 2e5 + 5;
const int MAXLog = 18;
int n;
vector <int> graph[MAXN];
bool solveDP(int s, int e, int l, int r)
{
if(s<l || e>r) return false;
vector <bool> used[2];
used[0].assign(n+5, false);
used[1].assign(n+5, false);
function <void(int, int)> DFS = [&](int x, int state)
{
if(used[state][x]==true) return;
used[state][x] = true;
//cout << state << " " << x << '\n';
if(state==0 && x>=l && x<=r) DFS(x, 1);
for(int y: graph[x])
{
if(state==0 && y<l) continue;
if(state==1 && y>r) continue;
DFS(y, state);
}
};
DFS(s, 0);
return used[1][e];
}
struct Element
{
int minVal, maxVal;
Element(){}
Element(int x)
{
this->minVal = x;
this->maxVal = x;
}
};
Element Merge(Element A, Element B)
{
Element out;
out.minVal = min(A.minVal, B.minVal);
out.maxVal = max(A.maxVal, B.maxVal);
return out;
}
int orderPos[MAXN];
vector <int> dfsOrder;
int logVal[MAXN];
Element sparse[20][MAXN];
void initLine()
{
int root = -1;
for(int x = 0;x<n;x++)
{
if(graph[x].size()==1)
{
root = x;
break;
}
}
function <void(int, int)> DFS = [&](int x, int last)
{
orderPos[x] = dfsOrder.size();
dfsOrder.push_back(x);
for(int y: graph[x])
{
if(y==last) continue;
DFS(y, x);
}
};
DFS(root, -1);
for(int i = 0;i<n;i++) sparse[0][i] = Element(dfsOrder[i]);
for(int i = 1;i<=MAXLog;i++)
{
for(int j = 0;j<n;j++)
{
if(j+(1<<(i-1))<n)
sparse[i][j] = Merge(sparse[i-1][j], sparse[i-1][j+(1<<(i-1))]);
else
sparse[i][j] = sparse[i-1][j];
}
}
logVal[0] = logVal[1] = 0;
for(int i = 2;i<=n;i++) logVal[i] = logVal[i/2] + 1;
}
Element getSegment(int l, int r)
{
int log2 = logVal[r-l+1];
return Merge(sparse[log2][l], sparse[log2][r-(1<<log2)+1]);
}
bool solveLine1(int S, int E, int L, int R)
{
if(S<L || E>R) return false;
int sPos = orderPos[S];
int ePos = orderPos[E];
int ind1, ind2;
assert(sPos<ePos);
int l = sPos, r = ePos, mid;
while(l+1<r)
{
mid = (l+r)/2;
if(getSegment(sPos, mid).minVal>=L) l = mid;
else r = mid - 1;
}
if(getSegment(sPos, r).minVal>=L) ind1 = r;
else if(getSegment(sPos, l).minVal>=L) ind1 = l;
l = sPos, r = ePos, mid;
while(l+1<r)
{
mid = (l+r)/2;
if(getSegment(mid, ePos).maxVal<=R) r = mid;
else l = mid + 1;
}
if(getSegment(l, ePos).maxVal<=R) ind2 = l;
else if(getSegment(r, ePos).maxVal<=R) ind2 = r;
//cout << ind1 << " " << ind2 << '\n';
return (ind1>=ind2);
}
bool solveLine2(int S, int E, int L, int R)
{
swap(S, E);
if(S>R || E<L) return false;
int sPos = orderPos[S];
int ePos = orderPos[E];
int ind1, ind2;
int l = sPos, r = ePos, mid;
while(l+1<r)
{
mid = (l+r)/2;
if(getSegment(sPos, mid).maxVal<=R) l = mid;
else r = mid - 1;
}
if(getSegment(sPos, r).maxVal<=R) ind1 = r;
else if(getSegment(sPos, l).maxVal<=R) ind1 = l;
l = sPos, r = ePos, mid;
while(l+1<r)
{
mid = (l+r)/2;
if(getSegment(mid, ePos).minVal>=L) r = mid;
else l = mid + 1;
}
if(getSegment(l, ePos).minVal>=L) ind2 = l;
else ind2 = r;
//cout << ind1 << " " << ind2 << '\n';
return (ind1>=ind2);
}
bool solveLine(int S, int E, int L, int R)
{
if(orderPos[S]<orderPos[E]) return solveLine1(S, E, L, R);
return solveLine2(S, E, L, R);
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y,
vector<int> S, vector<int> E,
vector<int> L, vector<int> R)
{
n = N;
for(int i = 0;i<X.size();i++)
{
graph[ X[i] ].push_back(Y[i]);
graph[ Y[i] ].push_back(X[i]);
}
vector <int> queryAnswers;
if(n<=6000 && X.size()<=6000 && S.size())
{
for(int i = 0;i<S.size();i++)
{
queryAnswers.push_back(solveDP(S[i], E[i], L[i], R[i]));
}
}
else
{
initLine();
for(int i = 0;i<S.size();i++)
{
queryAnswers.push_back(solveLine(S[i], E[i], L[i], R[i]));
}
}
return queryAnswers;
}
/*
6 6 3
5 1
1 2
1 3
3 4
3 0
5 2
4 2 1 2
4 2 2 2
5 4 3 4
6 5 2
0 2
2 1
1 5
5 4
4 3
0 1 0 2
1 0 1 2
*0 2 1 5 4 3
*/
