#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 1 << 18;
int n,m,q,st,en;
vector<int> adj[N];
int idx[N],wha[N];
struct node
{
int mn,mx;
friend node operator+(const node &a,const node &b)
{
node ret;
ret.mx = max(a.mx,b.mx);
ret.mn = min(a.mn,b.mn);
return ret;
}
}tree[N << 1];
void dfs(int u,int p,int k)
{
idx[u] = k,wha[k] = u;
for(int v : adj[u]) if(v!=p) dfs(v,u,k+1);
}
void build(int l,int r,int idx)
{
if(l==r) return void(tree[idx] = {wha[l],wha[l]});
int m = (l+r)/2;
build(l,m,idx*2),build(m+1,r,idx*2+1);
tree[idx] = tree[idx*2]+tree[idx*2+1];
}
node read(int l,int r,int idx,int x,int y)
{
if(x>r or y<l) return {INT_MAX,INT_MIN};
if(x<=l and y>=r) return tree[idx];
int m = (l+r)/2;
return read(l,m,idx*2,x,y)+read(m+1,r,idx*2+1,x,y);
}
int ltorx(int l,int r,int mn,int mx)
{
int lx = l;
while(l<r)
{
int m = (l+r+1)/2;
if(read(0,n-1,1,lx,m).mn>=mn) l = m;
else r = m-1;
}
return l;
}
int ltorn(int l,int r,int mn,int mx)
{
int lx = l;
while(l<r)
{
int m = (l+r+1)/2;
if(read(0,n-1,1,lx,m).mx<=mx) l = m;
else r = m-1;
}
return l;
}
int rtolx(int l,int r,int mn,int mx)
{
int rx = r;
while(l<r)
{
int m = (l+r)/2;
if(read(0,n-1,1,m,rx).mn>=mn) r = m;
else l = m+1;
}
return l;
}
int rtoln(int l,int r,int mn,int mx)
{
int rx = r;
while(l<r)
{
int m = (l+r)/2;
if(read(0,n-1,1,m,rx).mx<=mx) r = m;
else l = m+1;
}
return l;
}
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,m = x.size(),q = s.size();
for(int i = 0;i < m;i++)
{
int a = x[i],b = y[i];
adj[a].push_back(b);
adj[b].push_back(a);
}
for(int i = 0;i < n;i++) if(adj[i].size()==1) st = i;
dfs(st,st,0);
build(0,n-1,1);
vector<int> ans;
for(int i = 0;i < q;i++)
{
int fl,fr;
if(idx[s[i]]<idx[e[i]]) fl = ltorx(idx[s[i]],idx[e[i]],l[i],n-1),fr = rtoln(idx[s[i]],idx[e[i]],0,r[i]);
else fl = ltorn(idx[e[i]],idx[s[i]],0,r[i]),fr = rtolx(idx[e[i]],idx[s[i]],l[i],n-1);
ans.push_back(fl>=fr);
}
return ans;
}
