#include "werewolf.h"
#include <cassert>
#include <algorithm>
#include <functional>
#include <numeric>
template<typename T> bool ckmax(T& a, const T& b) {return b>a?a=b,1:0;}
template<typename T> bool ckmin(T& a, const T& b) {return b<a?a=b,1:0;}
const int MN = 2e5+10;
const int MQ = 2e5+10;
struct DSU
{
int S;
std::vector<int> p;
DSU(int _S): S(_S), p(_S, -1) {}
int find(int n) {return p[n]==-1 ? n : p[n] = find(p[n]);}
bool merge(int a, int b) // b into a
{
a=find(a), b=find(b);
if(a==b) return 0;
p[b]=a; // no rank
return 1;
}
};
struct ST
{
public:
int S;
std::vector<int> v;
ST(int _S=0): S(_S), v(4*_S, -1) {}
void upd(int n, int l, int r, int q, int val)
{
if(r-l>1)
{
int m=l+(r-l)/2;
if(q < m) upd(n<<1, l, m, q, val);
else upd(n<<1|1, m, r, q, val);
v[n]=std::max(v[n<<1], v[n<<1|1]);
}
else
v[n]=val;
}
void upd(int q, int val) {upd(1, 0, S, q, val);}
int qry(int n, int l, int r, int ql, int qr)
{
if(ql <= l&&r <= qr) return v[n];
if(r-l>1)
{
int m=l+(r-l)/2, f=-1;
if(ql < m) ckmax(f, qry(n<<1, l, m, ql, qr));
if(m < qr) ckmax(f, qry(n<<1|1, m, r, ql, qr));
return f;
}
assert(0);
return -1;
}
int qry(int ql, int qr) {return qry(1, 0, S, ql, qr);}
};
int N, M, Q;
std::vector<int> a[MN], t[2][MN], ans, todo[MN];
int pre[2][MN], post[2][MN], ord[2][MN], ctr[2];
template<int T>
void dfs(int n, int p=-1)
{
ord[T][ctr[T]]=n;
pre[T][n]=ctr[T]++;
for(int x:t[T][n])
if(x!=p)
dfs<T>(x, n);
post[T][n]=ctr[T];
}
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) {
::N=N;
M=X.size();
Q=S.size();
ans.assign(Q, -1);
for(int i=0;i<M;++i)
{
a[X[i]].push_back(Y[i]);
a[Y[i]].push_back(X[i]);
}
std::vector<int> ss(Q, -1), es(Q, -1); // start/end subtrees
//human tree
{
std::vector<int> ord(Q);
std::iota(ord.begin(), ord.end(), 0);
std::sort(ord.begin(), ord.end(), [&](int u, int v){return L[u]>L[v];});
DSU dsu(N);
for(int i=N-1, j=0;i>=0;--i)
{
for(int x:a[i])
{
int y=dsu.find(x);
if(i < x && dsu.merge(i, y))
t[0][i].push_back(y), t[0][y].push_back(i);
}
for(;j < Q && L[ord[j]]==i;++j)
ss[ord[j]]=dsu.find(S[ord[j]]);
}
}
//werewolf tree
{
std::vector<int> ord(Q);
std::iota(ord.begin(), ord.end(), 0);
std::sort(ord.begin(), ord.end(), [&](int u, int v){return R[u]<R[v];});
DSU dsu(N);
for(int i=0, j=0;i<N;++i)
{
for(int x:a[i])
{
int y=dsu.find(x);
if(x < i && dsu.merge(i, y))
t[1][i].push_back(y), t[1][y].push_back(i);
}
for(;j < Q && R[ord[j]]==i;++j)
es[ord[j]]=dsu.find(E[ord[j]]);
}
}
dfs<0>(0);
dfs<1>(N-1);
for(int i=0;i<Q;++i)
todo[post[1][es[i]]].push_back(i);
ST segtree(N);
for(int i=0;i<N;++i)
{
segtree.upd(pre[0][ord[1][i]], i); // add ord[1][i]
for(int x:todo[i+1])
{
ans[x] = segtree.qry(pre[0][ss[x]], post[0][ss[x]]) >= pre[1][es[x]];
//printf("\t%d: %d\n", x, segtree.qry(pre[0][ss[x]], post[0][ss[x]]));
}
}
return ans;
}
