#include<fstream>
#include<vector>
#include<algorithm>
#include<cstring>
#include "werewolf.h"
#define DIM 200005
#define f first
#define s second
using namespace std;
static int n, q, nr;
static int t[DIM], aint[4 * DIM], d[DIM];
static pair<int, int> p[2][DIM];
static vector<int> v[DIM], vt[2][DIM], sol;
struct str{
int ind, x, y, st, dr, p1, u1, p2, u2;
};
static str w[DIM];
int cmp1(str a, str b){
return a.st > b.st;
}
int cmp2(str a, str b){
return a.dr < b.dr;
}
int cmp3(str a, str b){
return a.p1 > b.p1;
}
int rad(int x){
int y, aux;
y = x;
while(t[y] != 0){
y = t[y];
}
while(t[x] != 0){
aux = t[x];
t[x] = y;
x = aux;
}
return y;
}
void update(int nod, int st, int dr, int p, int val){
if(st == dr){
aint[nod] = val;
}
else{
int mid = (st + dr) / 2;
if(p <= mid){
update(2 * nod, st, mid, p, val);
}
else{
update(2 * nod + 1, mid + 1, dr, p, val);
}
aint[nod] = min(aint[2 * nod], aint[2 * nod + 1]);
}
}
int query(int nod, int st, int dr, int p, int u){
if(p <= st && dr <= u){
return aint[nod];
}
else{
int mid = (st + dr) / 2;
int x, y;
x = y = n + 1;
if(p <= mid){
x = query(2 * nod, st, mid, p, u);
}
if(u > mid){
y = query(2 * nod + 1, mid + 1, dr, p, u);
}
return min(x, y);
}
}
void dfs(int nod, int ind){
p[ind][nod].f = ++nr;
for(int i = 0; i < vt[ind][nod].size(); i++){
dfs(vt[ind][nod][i], ind);
}
p[ind][nod].s = nr;
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
int i, j, nod, u, r;
n = N;
q = S.size();
sol.resize(q);
for(i = 0; i < n - 1; i++){
X[i]++; Y[i]++;
v[ X[i] ].push_back(Y[i]);
v[ Y[i] ].push_back(X[i]);
}
for(i = 0; i < q; i++){
w[i + 1] = {i, S[i] + 1, E[i] + 1, L[i] + 1, R[i] + 1, 0, 0, 0, 0};
}
sort(w + 1, w + q + 1, cmp1);
u = 1;
for(i = n; i >= 1; i--){
for(j = 0; j < v[i].size(); j++){
nod = v[i][j];
r = rad(nod);
if(nod > i && r != i){
t[r] = i;
vt[0][i].push_back(r);
}
}
while(w[u].st == i){
w[u].p1 = rad(w[u].x);
u++;
}
}
memset(t, 0, sizeof(t) );
sort(w + 1, w + q + 1, cmp2);
u = 1;
for(i = 1; i <= n; i++){
for(j = 0; j < v[i].size(); j++){
nod = v[i][j];
r = rad(nod);
if(nod < i && r != i){
t[r] = i;
vt[1][i].push_back(r);
}
}
while(w[u].dr == i){
w[u].p2 = rad(w[u].y);
u++;
}
}
dfs(1, 0);
nr = 0;
dfs(n, 1);
for(i = 1; i <= n; i++){
d[ p[0][i].f ] = i;
}
for(i = 1; i <= q; i++){
nod = w[i].p1;
w[i].p1 = p[0][nod].f;
w[i].u1 = p[0][nod].s;
nod = w[i].p2;
w[i].p2 = p[1][nod].f;
w[i].u2 = p[1][nod].s;
}
sort(w + 1, w + q + 1, cmp3);
u = 1;
for(i = 1; i <= 4 * n; i++){
aint[i] = n + 1;
}
for(i = n; i >= 1; i--){
update(1, 1, n, p[1][ d[i] ].f, i);
while(w[u].p1 == i){
if( query(1, 1, n, w[u].p2, w[u].u2) <= w[u].u1){
sol[ w[u].ind ] = 1;
}
else{
sol[ w[u].ind ] = 0;
}
u++;
}
}
return sol;
}
