#include "werewolf.h"
#include <bits/stdc++.h>
#define fr first
#define sc second
#define mk make_pair
#define pb push_back
#define all(s) s.begin(), s.end()
using namespace std;
vector < vector <int> > g;
const int N = 2e5 + 5;
int n, m, beg, ind[N], a[N], t[2][20][N], lg[N];
void dfs (int v, int p = -1)
{
beg = v;
for (auto to : g[v])
{
if (to == p) continue;
dfs(to, v);
}
}
void Dfs (int v, int i, int p = -1)
{
ind[v] = i;
a[i] = v;
for (auto to : g[v])
{
if (to == p) continue;
Dfs(to, i + 1, v);
}
}
void build ()
{
lg[1] = 0;
for (int i = 2; i <= n; i++)
lg[i] = lg[i / 2] + 1;
for (int i = 1; i <= n; i++){
t[0][0][i] = a[i], t[1][0][i] = a[i];
}
for (int i = 1; i < 20; i++)
{
for (int j = (1 << i); j <= n; j++)
t[0][i][j] = min( t[0][i - 1][j], t[0][i - 1][j - (1 << (i - 1) ) ] ),
t[1][i][j] = max( t[1][i - 1][j], t[1][i - 1][j - (1 << (i - 1) ) ] );
}
}
inline int get (int l, int r, int typ)
{
int pw = lg[r - l];
if (typ == 0){
return min( t[0][pw][r], t[0][pw][l + (1 << pw) - 1] );
}
else{
return max( t[1][pw][r], t[1][pw][l + (1 << pw) - 1] );
}
}
inline pair <int, int> calc (int pos, int l, int r)
{
pair <int, int> res;
int L = 0, R = n;
while (R - L > 1)
{
int md = (L + R) >> 1;
if ( pos - md >= 1 && get( pos - md, pos, 0 ) >= l && get( pos - md, pos, 1 ) <= r )
L = md;
else
R = md;
}
res.fr = pos - L;
L = 0, R = n;
while (R - L > 1)
{
int md = (L + R) >> 1;
if ( pos + md <= n && get( pos, pos + md, 0 ) >= l && get( pos, pos + md, 1 ) <= r )
L = md;
else
R = md;
}
res.sc = pos + L;
return res;
}
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();
g.resize(n + 1);
for (int i = 0; i < m; i++)
g[ x[i] ].pb( y[i] ),
g[ y[i] ].pb( x[i] );
dfs(0);
Dfs(beg, 1);
build ();
int q = s.size();
vector <int> ans;
for (int i = 0; i < q; i++)
{
if ( s[i] < l[i] || e[i] > r[i] )
{
ans.pb(0);
continue;
}
pair <int, int> a = calc( ind[s[i]], l[i], n - 1 );
pair <int, int> b = calc( ind[e[i]], 0, r[i] );
if (a.fr > b.sc || b.fr > a.sc)
ans.pb(0);
else
ans.pb(1);
}
return ans;
}
/**
6 5 0
2 5
5 6
0 1
1 3
3 4
**/
