#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
struct segtree{
struct Node{
int mn, mx;
};
int size = 1;
vector<Node> stree;
void init(int N){
while(size < N) size <<= 1;
stree.assign(4*size, {N + 1, -1});
}
void build(int x, int lx, int rx){
if(rx - lx == 1){
return;
}
int m = (lx + rx) / 2;
build(2*x+1, lx, m);
build(2*x+2, m, rx);
stree[x].mx = max(stree[2*x+1].mx, stree[2*x+2].mx);
stree[x].mn = min(stree[2*x+1].mn, stree[2*x+2].mn);
}
void upd(int i, int v, int x, int lx, int rx){
if(rx - lx == 1){
stree[x] = {v, v};
return;
}
int m = (lx + rx) / 2;
if(i < m) upd(i, v, 2*x+1, lx, m);
else upd(i, v, 2*x+2, m, rx);
stree[x].mx = max(stree[2*x+1].mx, stree[2*x+2].mx);
stree[x].mn = min(stree[2*x+1].mn, stree[2*x+2].mn);
}
void upd(int i, int v){
upd(i, v, 0, 0, size);
}
int get_first_mn(int l, int r, int v, int x, int lx, int rx){
if(lx >= r || rx <= l) return -1;
if(stree[x].mn >= v) return -1;
if(rx - lx == 1){
return lx;
}
int res = -1;
int m = (lx + rx) / 2;
res = get_first_mn(l, r, v, 2*x+1, lx, m);
if(res == -1) res = get_first_mn(l, r, v, 2*x+2, m, rx);
return res;
}
int get_last_mx(int l, int r, int v, int x, int lx, int rx){
if(lx >= r || rx <= l) return -1;
if(stree[x].mx <= v) return -1;
if(rx - lx == 1){
return lx;
}
int res = -1;
int m = (lx + rx) / 2;
res = get_last_mx(l, r, v, 2*x+2, m, rx);
if(res == -1){
res = get_last_mx(l, r, v, 2*x+1, lx, m);
}
return res;
}
int get_last_mn(int l, int r, int v, int x, int lx, int rx){
if(lx >= r || rx <= l) return -1;
if(stree[x].mn >= v) return -1;
if(rx - lx == 1){
return lx;
}
int res = -1;
int m = (lx + rx) / 2;
res = get_last_mn(l, r, v, 2*x+2, m, rx);
if(res == -1) res = get_last_mn(l, r, v, 2*x+1, lx, m);
return res;
}
int get_first_mx(int l, int r, int v, int x, int lx, int rx){
if(lx >= r || rx <= l) return -1;
if(stree[x].mx <= v) return -1;
if(rx - lx == 1){
return lx;
}
int res = -1;
int m = (lx + rx) / 2;
res = get_first_mx(l, r, v, 2*x+1, lx, m);
if(res == -1){
res = get_first_mx(l, r, v, 2*x+2, m, rx);
}
return res;
}
int get_first_mn(int l, int r, int v){
return get_first_mn(l, r, v, 0, 0, size);
}
int get_last_mx(int l, int r, int v){
return get_last_mx(l, r, v, 0, 0, size);
}
int get_last_mn(int l, int r, int v){
return get_last_mn(l, r, v, 0, 0, size);
}
int get_first_mx(int l, int r, int v){
return get_first_mx(l, r, v, 0, 0, size);
}
}st;
const int N = 1e5 + 10;
int id[N];
std::vector<int> ord;
std::vector<int> adj[N];
void dfs(int node, int parent){
id[node] = ord.size();
ord.push_back(node);
for(auto i : adj[node]){
if(i == parent) continue;
dfs(i, node);
}
}
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();
for (int i = 0; i < X.size(); i++) {
adj[X[i]].push_back(Y[i]);
adj[Y[i]].push_back(X[i]);
}
for(int i = 0; i < N; i++){
if(adj[i].size() == 1){
dfs(i, -1);
break;
}
}
st.init(N);
for(int i = 0; i < N; i++){
st.upd(i, ord[i]);
}
st.build(0, 0, st.size);
std::vector<int> A(Q);
for (int i = 0; i < Q; ++i) {
if(S[i] < L[i] || E[i] > R[i]){
A[i] = 0;
continue;
}
if(S[i] == E[i]){
if(L[i] <= S[i] && S[i] <= R[i]){
A[i] = 1;
}else{
A[i] = 0;
}
}else{
if(id[S[i]] < id[E[i]]){
int fr = st.get_first_mn(id[S[i]], id[E[i]] + 1, L[i]);
if(fr == -1){
int ls = st.get_last_mx(id[S[i]], id[E[i]] + 1, R[i]);
if(ls == -1){
A[i] = 1;
}else{
if(st.get_last_mx(ls + 1, id[E[i]] + 1, L[i] - 1) != -1){
A[i] = 1;
}else{
A[i] = 0;
}
}
}else{
int ls = st.get_last_mx(id[S[i]], fr, R[i]);
if(ls == -1){
if(st.get_first_mn(id[S[i]], fr, R[i] + 1) != -1){
if(st.get_last_mx(fr, id[E[i]] + 1, R[i]) != -1){
A[i] = 0;
}else{
A[i] = 1;
}
}else{
A[i] = 0;
}
}else{
if(st.get_first_mn(ls, fr, R[i] + 1) != -1){
if(st.get_last_mx(fr, id[E[i]] + 1, R[i]) != -1){
A[i] = 0;
}else{
A[i] = 1;
}
}else{
A[i] = 0;
}
}
}
}else{
int fr = st.get_last_mn(id[S[i]], id[E[i]] + 1, L[i]);
if(fr == -1){
int ls = st.get_first_mx(id[S[i]], id[E[i]] + 1, R[i]);
if(ls == -1){
A[i] = 1;
}else{
if(st.get_last_mx(id[S[i]], ls, L[i] - 1) != -1){
A[i] = 1;
}else{
A[i] = 0;
}
}
}else{
int ls = st.get_first_mx(fr, id[E[i]] + 1, R[i]);
if(ls == -1){
if(st.get_last_mn(fr + 1, id[E[i]] + 1, R[i] + 1) != -1){
if(st.get_first_mx(id[S[i]], fr, R[i]) != -1){
A[i] = 0;
}else{
A[i] = 1;
}
}else{
A[i] = 0;
}
}else{
if(st.get_last_mn(fr, ls, R[i] + 1) != -1){
if(st.get_first_mx(id[S[i]], fr, R[i]) != -1){
A[i] = 0;
}else{
A[i] = 1;
}
}else{
A[i] = 0;
}
}
}
}
}
}
return A;
}
