#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;
const int M=6e5+10;
const int K=1<<19;
struct KRT{
vector<vector<int>> adj,d;
vector<int> pa,dep,ag,lb,rb,rev,wi;
int cnt,ti;
void init(int n){
pa.resize(M);
for(int i=1;i<=n;i++) pa[i]=i;
cnt=n;
adj.resize(M);
dep.resize(M,0);
ag.resize(M,0);
d.resize(M,vector<int>(20,0));
lb.resize(M),rb.resize(M),rev.resize(M),wi.resize(M);
}
int root(int x){if(pa[x]==x) return x; return pa[x]=root(pa[x]);}
void add(int u,int v,int w){
int ru=root(u),rv=root(v);
cnt++;
pa[cnt]=pa[ru]=pa[rv]=cnt;
wi[cnt]=w;
adj[cnt].push_back(ru);
if(ru!=rv) adj[cnt].push_back(rv);
d[ru][0]=d[rv][0]=cnt;
}
void dfs(int u,int p){
int c=0;
lb[u]=INT_MAX,rb[u]=INT_MIN;
for(auto v:adj[u]){
if(v==p) continue;
dep[v]=dep[u]+1;
dfs(v,u);
lb[u]=min(lb[u],lb[v]);
rb[u]=max(rb[u],rb[v]);
c++;
}
if(c==0) ag[u]=++ti,lb[u]=rb[u]=ti,rev[ti]=u;
}
void initlca(){
d[cnt][0]=cnt;
for(int i=1;i<=19;i++){
for(int j=1;j<=cnt;j++) d[j][i]=d[d[j][i-1]][i-1];
}
dfs(cnt,cnt);
}
//find upmost such that still able to traverse in weight (L,N) for human
int fd(int x,int st){
for(int i=19;i>=0;i--) if(wi[d[st][i]]>=x) st=d[st][i];
return st;
}
//find upmost such that still able to traverse in weight (1,R) for wolf
int fdb(int x,int st){
for(int i=19;i>=0;i--) if(wi[d[st][i]]<=x) st=d[st][i];
return st;
}
}wf,hm;
struct UWU{
vector<vector<int>> s;
vector<int> arr;
void init(){
s.resize(K);
arr.resize(K);
}
void build(int l,int r,int idx){
if(l==r){
s[idx].push_back(arr[l]);
return;
}
int ia=0,ib=0;
int m=(l+r)/2;
build(l,m,idx*2);
build(m+1,r,idx*2+1);
while(ia<s[idx*2].size() && ib<s[idx*2+1].size()){
if(s[idx*2][ia]<=s[idx*2+1][ib]) s[idx].push_back(s[idx*2][ia++]);
else s[idx].push_back(s[idx*2+1][ib++]);
}
while(ia<s[idx*2].size()) s[idx].push_back(s[idx*2][ia++]);
while(ib<s[idx*2+1].size()) s[idx].push_back(s[idx*2+1][ib++]);
}
//find minimal value in range arr[l]...arr[r] which >=val
int query(int l,int r,int idx,int a,int b,int val){
if(a>r || b<l) return INT_MAX;
if(a<=l && b>=r){
auto it=lower_bound(s[idx].begin(),s[idx].end(),val);
if(it==s[idx].end()) return INT_MAX;
return *it;
}
int m=(l+r)/2;
return min(query(l,m,idx*2,a,b,val),query(m+1,r,idx*2+1,a,b,val));
}
}treee;
std::vector<int> check_validity(int N,vector<int> X, vector<int> Y,vector<int> S,vector<int> E,
vector<int> L, std::vector<int> R) {
vector<int> ret(S.size());
int m=X.size(),q=S.size();
hm.init(N),wf.init(N);
treee.init();
vector<tuple<int,int,int>> edge;
//make KRT for human route
for(int i=0;i<m;i++){
X[i]++,Y[i]++;
edge.push_back({min(X[i],Y[i]),X[i],Y[i]});
}
sort(edge.begin(),edge.end(),greater<tuple<int,int,int>>());
for(auto [w,u,v]:edge) hm.add(u,v,w);
hm.initlca();
//wolffff
edge.clear();
for(int i=0;i<m;i++){
edge.push_back({max(X[i],Y[i]),X[i],Y[i]});
}
sort(edge.begin(),edge.end());
for(auto [w,u,v]:edge) wf.add(u,v,w);
wf.initlca();
for(int i=1;i<=N;i++) treee.arr[i]=hm.ag[wf.rev[i]];
treee.build(1,N,1);
for(int i=0;i<q;i++){
S[i]++,E[i]++,L[i]++,R[i]++;
//node range (lb[lc],rb[lc])(hm index) os able to traverse by human
int lc=hm.fd(L[i],S[i]);
int lcw=wf.fdb(R[i],E[i]);
int mn=treee.query(1,N,1,wf.lb[lcw],wf.rb[lcw],hm.lb[lc]);
ret[i]=mn<=hm.rb[lc];
}
return ret;
}
