#include "werewolf.h"
#include <queue>
#include <algorithm>
#include <cstdlib>
#include <cassert>
#include <iostream>
using namespace std;
typedef vector<int> VI;
typedef vector<VI> VVI;
const int INF = 1000000000;
struct SegmentTree {
int N;
vector<int> MIN, MAX;
SegmentTree(const vector<int>& A) {
N = A.size();
MIN = vector<int>(4*N);
MAX = vector<int>(4*N);
build(A, 1, 0, N-1);
}
void build(const vector<int>& A, int node, int L, int R) {
if (L == R) {
MIN[node] = A[L];
MAX[node] = A[L];
return;
}
int mid = (L + R)/2;
build(A, node*2, L, mid);
build(A, node*2+1, mid+1, R);
MIN[node] = min(MIN[node*2], MIN[node*2+1]);
MAX[node] = max(MAX[node*2], MAX[node*2+1]);
}
int query_min(int qL, int qR) {
return query_min(qL, qR, 1, 0, N-1);
}
int query_min(int qL, int qR, int node, int L, int R) {
if (qR < L || qL > R) return +INF;
if (qL <= L && R <= qR) return MIN[node];
int mid = (L + R)/2;
return min(query_min(qL, qR, node*2, L, mid),
query_min(qL, qR, node*2+1, mid+1, R));
}
int query_max(int qL, int qR) {
return query_max(qL, qR, 1, 0, N-1);
}
int query_max(int qL, int qR, int node, int L, int R) {
if (qR < L || qL > R) return -INF;
if (qL <= L && R <= qR) return MAX[node];
int mid = (L + R)/2;
return max(query_max(qL, qR, node*2, L, mid),
query_max(qL, qR, node*2+1, mid+1, R));
}
};
VVI get_graph(int N, const VI& X, const VI& Y) {
VVI G(N);
int M = X.size();
for (int j = 0; j < M; ++j) {
int u = X[j], v = Y[j];
G[u].push_back(v);
G[v].push_back(u);
}
return G;
}
VI bfs(int N, VVI& adj, int src, int dst) {
queue<int> q;
q.push(src);
VI D(N, INF);
D[src] = 0;
VI P(N, -1);
while (!q.empty()) {
int u = q.front(); q.pop();
if (u == dst) {
VI path;
for (int x = dst; x >= 0; x = P[x])
path.push_back(x);
reverse(path.begin(), path.end());
return path;
}
for (int v : adj[u]) {
if (D[v] > D[u] + 1) {
D[v] = D[u] + 1;
P[v] = u;
q.push(v);
}
}
}
return {};
}
bool is_subtask3(int N, int M, VVI& adj, VI& line) {
if (M != N-1)
return false;
VI nodes_deg1;
for (int u = 0; u < N; ++u) {
if (adj[u].size() > 2)
return false;
if (adj[u].size() == 1)
nodes_deg1.push_back(u);
}
assert(nodes_deg1.size() == 2);
line = bfs(N, adj, nodes_deg1[0], nodes_deg1[1]);
assert(line.size() == N);
return true;
}
bool query(SegmentTree& st, const VI& line, const VI& pos,
int src, int dst, int L, int R) {
int src_pos = pos[src], dst_pos = pos[dst];
if (src_pos < dst_pos) {
// de izquierda a derecha
if (st.query_min(src_pos, dst_pos) >= L)
return true;
// binary search para encontrar el primer nodo (a la derecha de src_pos)
// mas pequenio que L
int lo = src_pos, hi = dst_pos;
int m = -1;
while (lo <= hi) {
int mid = (lo + hi) / 2;
int cur = st.query_min(lo, mid);
if (cur < L) {
m = mid;
hi = mid-1;
}
else {
lo = mid+1;
}
}
assert(m != -1 && m > src_pos);
assert(line[m-1] >= L);
// m es la posicion del primer nodo mas pequenio que L
if (line[m-1] > R)
return false;
if (st.query_max(m, dst_pos) > R)
return false;
}
else {
// de derecha a izquierda
if (st.query_min(dst_pos, src_pos) >= L)
return true;
// binary search para encontrar el primer nodo (a la izquierda de src_pos)
// mas pequenio que L
int lo = dst_pos, hi = src_pos;
int m = -1;
while (lo <= hi) {
int mid = (lo + hi) / 2;
if (st.query_min(mid, hi) < L) {
m = mid;
lo = mid+1;
}
else {
hi = mid-1;
}
}
assert(m != -1 && m < src_pos);
assert(line[m+1] >= L);
// m es la posicion del primer nodo mas pequenio que L
if (line[m+1] > R)
return false;
if (st.query_max(dst_pos, m) > R)
return false;
}
return true;
}
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) {
int Q = S.size();
std::vector<int> res(Q);
VVI adj = get_graph(N, X, Y);
VI line;
if (is_subtask3(N, X.size(), adj, line)) {
VI pos(N);
for (int i = 0; i < N; ++i) {
int u = line[i];
pos[u] = i;
}
SegmentTree st(line);
for (int q = 0; q < Q; ++q) {
res[q] = query(st, line, pos, S[q], E[q], L[q], R[q]);
}
return res;
}
for (int i = 0; i < Q; ++i) {
res[i] = rand() % 2;
}
return res;
}
