#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;
const int N = 200005;
vector<int> gr[N];
vector<int> amin[N], amax[N];
int dmin[20][N], dmax[20][N];
int pmin[N], pmax[N];
int findt(int x, int p[]){
if(x == p[x])
return x;
p[x] = findt(p[x], p);
return p[x];
}
void join (int x, int y, int p[], int d[20][N]){ // x tatal de care unesc pe fiul y
if(findt(x,p) != findt(y,p)){
y = findt(y,p);
p[y] = x;
d[0][y] = x;
}
}
struct intv{
int l,r;
};
intv itvmin[N];
int postord[N];
void dfsmin(int nod,int dad, int &cnt){
cnt++;
itvmin[nod].l = cnt;
postord[cnt] = nod;
for(auto x: amin[nod]){
if(x!=dad){
dfsmin(x,nod,cnt);
}
}
itvmin[nod].r = cnt;
}
intv itvmax[N];
void dfsmax(int nod,int dad, int &cnt){
cnt++;
itvmax[nod].l = cnt;
for(auto x: amax[nod]){
if(x!=dad){
dfsmax(x,nod,cnt);
}
}
itvmax[nod].r = cnt;
}
struct querys{
int l;
int c1,c2;
int type;
int id;
};
bool cmpquerys(querys a, querys b){
return a.l < b.l;
}
int aib[N];
void update(int poz,int val){
for(int i = poz; i < N ; i+= i&(-i))
aib[i] += val;
}
int query(int poz){
int ans = 0;
for(int i=poz; i>0; i-= i&(-i))
ans+=aib[i];
return ans;
}
std::vector<int> check_validity(int n, vector<int> X, vector<int> Y,vector<int> S, vector<int> E,vector<int> L, vector<int> R) {
for(int i = 0; i< X.size(); i++){
gr[X[i] + 1].push_back(Y[i] + 1);
gr[Y[i] + 1].push_back(X[i] + 1);
}
for(int i=1;i<=n;i++){
pmin[i] = pmax[i] = i;
}
for(int i=1; i<=n;i++){
for(auto j:gr[i]){
if(j < i){
join(i, j, pmax, dmax);
}
}
}
for(int i=1; i<=n; i++){
amax[dmax[0][i]].push_back(i);
amax[i].push_back(dmax[0][i]);
}
int cnt = 0;
dfsmax(n, 0, cnt);
for(int i = n; i>=1; i--){
for(auto j:gr[i]){
if(j > i){
join(i, j, pmin, dmin);
}
}
}
cnt = 0;
for(int i=1; i<=n; i++){
amin[dmin[0][i]].push_back(i);
amin[i].push_back(dmin[0][i]);
}
dfsmin(1, 0, cnt);
for(int log = 1; log < 20; log ++){
for(int i= 1; i<=n;i++){
dmin[log][i] = dmin[log-1][dmin[log-1][i]];
dmax[log][i] = dmax[log-1][dmax[log-1][i]];
}
}
int Q = S.size();
vector<querys> q;
for(int i = 0 ; i < Q ; i++){
int s = S[i] + 1;
int e = E[i] + 1;
int l = L[i] + 1;
int r = R[i] + 1;
for(int pas = 19; pas >= 0; pas--){
if(dmin[pas][s]!=0 && dmin[pas][s] >= l)
s = dmin[pas][s];
}
intv mn = itvmin[s];
for(int pas = 19; pas>=0; pas--){
if(dmax[pas][e]!=0 && dmax[pas][e] <= r)
e = dmax[pas][e];
}
intv mx = itvmax[e];
q.push_back({mn.l-1, mx.l, mx.r, -1, i});
q.push_back({mn.r, mx.l, mx.r, 1, i});
}
std::vector<int> A(Q);
sort(q.begin(),q.end(),cmpquerys);
int pc = 1;
for(auto qc:q){
while(pc <= qc.l){
update(itvmax[postord[pc]].l, 1);
pc++;
}
A[qc.id] += qc.type * (query(qc.c2) - query(qc.c1 - 1));
}
for(auto &a: A)
if(a > 0)
a = 1;
else
a = 0;
return A;
}
