#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
struct segment{
vector<int> mn, mx;
void build(int v, int l, int r, vector<int> &vec){
if(r-l == 1){
mn[v] = vec[l], mx[v] = vec[l];
return;
}
int m = (l+r)/2;
build(2*v, l, m, vec);
build(2*v+1, m, r, vec);
mn[v] = min(mn[2*v], mn[2*v+1]);
mx[v] = max(mx[2*v], mx[2*v+1]);
}
segment(int sz, vector<int> &vec){
mn.resize(4*sz, INT_MAX), mx.resize(4*sz, -1);
build(1, 0, sz, vec);
}
void upd(int v, int l, int r, int pos, int val){
if(r-l == 1){
mn[l] = val;
mx[l] = val;
}
int m = (l+r)/2;
if(pos < m) upd(2*v, l, m, pos, val);
else upd(2*v+1, m, r, pos, val);
mn[v] = min(mn[2*v], mn[2*v+1]);
mx[v] = max(mx[2*v], mx[2*v+1]);
}
pair<int,int> query(int v, int l, int r, int ql, int qr){
if(l >= qr or r <= ql) return {INT_MAX, -1};
if(l >= ql and r <= qr) return {mn[v], mx[v]};
int m = (l+r)/2;
auto left = query(2*v, l, m, ql, qr);
auto right = query(2*v+1, m, r, ql, qr);
return {min(left.first, right.first), max(left.second, right.second)};
}
};
std::vector<int> small(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){
vector<vector<int>> ad(N);
for(int i=0; i<X.size(); i++){
ad[X[i]].push_back(Y[i]);
ad[Y[i]].push_back(X[i]);
}
vector<int> vis(N);
function<void(int, int, int)> dfs = [&](int v, int mn, int mx){
vis[v] = 1;
for(int u: ad[v]){
if(vis[u] or u < mn or u > mx) continue;
dfs(u, mn, mx);
}
};
vector<int> ans(S.size());
for(int i=0; i<S.size(); i++){
vis.assign(N, 0);
dfs(S[i], L[i], N);
auto from_start = vis;
vis.assign(N, 0);
dfs(E[i], 0, R[i]);
auto from_end = vis;
for(int j=0; j<N; j++) if(from_start[j] and from_end[j]) ans[i] = 1;
}
return ans;
}
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){
if(N<=3000 and X.size()<=6000 and S.size()<=3000) return small(N, X, Y, S, E, L, R);
vector<vector<int>> ad(N);
for(int i=0; i<X.size(); i++){
ad[X[i]].push_back(Y[i]);
ad[Y[i]].push_back(X[i]);
}
if(X.size() != N-1) return {};
vector<int> vis;
function<void(int, int)> dfs = [&](int v, int p){
vis.push_back(v);
for(int u: ad[v]){
if(u == p) continue;
dfs(u, v);
}
};
vector<int> v;
dfs(0, -1);
int e1 = vis.back();
vis.clear();
dfs(e1, -1);
v = vis;
vector<int> pos(N);
for(int i=0; i<N; i++) pos[v[i]] = i;
segment st(N, v);
vector<int> ans(S.size());
for(int i=0; i<S.size(); i++){
if(pos[S[i]] < pos[E[i]]){
int l = pos[S[i]], r = pos[E[i]]+1;
while(r-l > 1){
int m = (l+r)/2;
auto [mn, mx] = st.query(1, 0, N, pos[S[i]], m+1);
if(mn >= L[i]) l = m;
else r = m;
}
if(st.query(1, 0, N, l, pos[E[i]]+1).second <= R[i]) ans[i] = 1;
}
else{
int l = pos[E[i]], r = pos[S[i]]+1;
while(r-l > 1){
int m = (l+r)/2;
auto [mn, mx] = st.query(1, 0, N, pos[E[i]], m+1);
if(mx <= R[i]) l = m;
else r = m;
}
if(st.query(1, 0, N, l, pos[S[i]]+1).first >= L[i]) ans[i] = 1;
}
}
return ans;
}
