#include "werewolf.h"
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define sz(x) (int)x.size()
using namespace std;
using VI = vector <int>;
using PII = pair <int, int>;
const int N = 2e5+1;
const int M = 3*N;
int n, m, q;
vector <int> paths[N];
int ans[N], p[N];
VI nums, res;
PII dp[N][20];
void dfs(int pos, int par = -1) {
// cout << pos << " ";
p[pos] = sz(nums);
dp[p[pos]][0] = {pos, pos};
nums.pb(pos);
for (auto el : paths[pos]) {
if (el == par) continue;
dfs(el, pos);
}
}
bool intersect(PII a, PII b) {
int x = a.ss - a.ff + 1;
int y = b.ss - b.ff + 1;
int l = min(a.ff, b.ff);
int r = max(a.ss, b.ss);
l = r - l + 1;
// cout << x << ' ' << y << ' ' << l << '\n';
return (x+y > l);
}
PII get(int l, int r) {
int p = 0, len = r - l + 1;
while((1<<p) <= len) p++;
p--;
return {
min(dp[l][p].ff, dp[r-(1<<p)+1][p].ff),
max(dp[l][p].ss, dp[r-(1<<p)+1][p].ss)
};
}
VI check_validity(int _N, VI X, VI Y, VI ST, VI ED, VI L, VI R) {
n = _N;
m = sz(X);
q = sz(ST);
for (int i = 0; i < m; i++) {
paths[X[i]].pb(Y[i]);
paths[Y[i]].pb(X[i]);
}
int st = 0;
while(sz(paths[st]) != 1) st++;
dfs(st);
for (int j = 1; j < 20; j++)
for (int i = 0; i < n; i++) {
dp[i][j] = {
min(dp[i][j-1].ff, dp[min(n-1, i+(1<<(j-1)))][j-1].ff),
max(dp[i][j-1].ss, dp[min(n-1, i+(1<<(j-1)))][j-1].ss)
};
}
for (int i = 0; i < q; i++) {
int a, b, c, d;
a = b = ST[i] = p[ST[i]];
c = d = ED[i] = p[ED[i]];
{
int l = 0, r = ST[i];
while(l <= r) {
int mid = (l+r)>>1;
PII cur = get(mid, ST[i]);
if (cur.ff >= L[i]) {
a = mid;
r = mid-1;
} else {
l = mid+1;
}
}
}
{
int l = ST[i], r = n-1;
while(l <= r) {
int mid = (l+r)>>1;
PII cur = get(ST[i], mid);
if (cur.ff >= L[i]) {
b = mid;
l = mid+1;
} else {
r = mid-1;
}
}
}
{
int l = 0, r = ED[i];
while(l <= r) {
int mid = (l+r)>>1;
PII cur = get(mid, ED[i]);
if (cur.ss <= R[i]) {
c = mid;
r = mid-1;
} else {
l = mid+1;
}
}
}
{
int l = ED[i], r = n-1;
while(l <= r) {
int mid = (l+r)>>1;
PII cur = get(ED[i], mid);
if (cur.ss <= R[i]) {
d = mid;
l=mid+1;
} else {
r = mid-1;
}
}
}
// cout << ST[i] << " " << ED[i] << '\n';
// cout << get(c, ED[i]).ss << " " << get(ED[i], d).ss << ' ' << R[i] << '\n';
// cout << a << ' ' << b << ' ' << c << ' ' << d << '\n';
res.pb(intersect({a, b}, {c, d}));
}
return res;
}
