#include "werewolf.h"
#include "bits/stdc++.h"
using namespace std;
#define FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define pb push_back
#define eb emplace_back
#define ins insert
#define f first
#define s second
#define cbr cerr<<"hi\n"
#define mmst(x, v) memset((x), v, sizeof ((x)))
#define siz(x) ll(x.size())
#define all(x) (x).begin(), (x).end()
#define lbd(x,y) (lower_bound(all(x),y)-x.begin())
#define ubd(x,y) (upper_bound(all(x),y)-x.begin())
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); //can be used by calling rng() or shuffle(A, A+n, rng)
inline long long rand(long long x, long long y) { return rng() % (y+1-x) + x; } //inclusivesss
string inline to_string(char c) {string s(1,c);return s;} template<typename T> inline T gcd(T a,T b){ return a==0?llabs(b):gcd(b%a,a); }
using ll=int;
using ld=long double;
#define FOR(i,s,e) for(ll i=s;i<=ll(e);++i)
#define DEC(i,s,e) for(ll i=s;i>=ll(e);--i)
using pi=pair<ll,ll>; using spi=pair<ll,pi>; using dpi=pair<pi,pi>;
#define LLINF ((long long)1e18)
#define INF int(1e9+1e6)
#define MAXN (200006)
ll n;
vector<ll> cost;
struct sparse_max {
int sp[19][MAXN];
void build(){
FOR(i,0,n-2)sp[0][i]=cost[i];
FOR(h,1,18){
for(ll i=0;i+(1<<h)-1<=n-2;++i){
sp[h][i]=max(sp[h-1][i],sp[h-1][i+(1<<(h-1))]);
}
}
}
ll rmq(ll x,ll y){
ll p=__builtin_clz(y-x+1) ^ 31;
return max(sp[p][x], sp[p][y-(1<<p)+1]);
}
} mini;
struct sparse_mi {
int sp[19][MAXN];
void build(){
FOR(i,0,n-2)sp[0][i]=cost[i];
FOR(h,1,18){
for(ll i=0;i+(1<<h)-1<=n-2;++i){
sp[h][i]=min(sp[h-1][i],sp[h-1][i+(1<<(h-1))]);
}
}
}
ll rmq(ll x,ll y){
ll p=__builtin_clz(y-x+1) ^ 31;
return min(sp[p][x], sp[p][y-(1<<p)+1]);
}
} maxi;
struct node2 {
int s,e,m;
vector<ll> v;
node2 *l,*r;
node2(int S,int E){
s=S,e=E,m=(s+e)>>1;
v.clear();
if(s^e)l=new node2(s,m),r=new node2(m+1,e);
}
void update(int x,ll nval){
if(s==e){
v.eb(nval);
return;
}
if(x>m)r->update(x,nval);else l->update(x,nval);
}
void prog(){
if(s==e)return;
l->prog(), r->prog();
ll co1=0, co2=0;
while(co1 < l->v.size() || co2 < r->v.size()){
if(co1 == l->v.size()) { v.eb(r->v[co2++]); continue; }
if(co2 == r->v.size()) { v.eb(l->v[co1++]); continue; }
if(l->v[co1] <= r->v[co2]) v.eb(l->v[co1++]);
else v.eb(r->v[co2++]);
}
v.resize(unique(all(v))-v.begin());
}
bool rmq(int x,int y,int a,int b){
if(s==x&&e==y){
ll ind = lbd(v, a);
if(ind == v.size() || v[ind] > b) return 0;
return 1;
}
if(x>m) return r->rmq(x,y,a,b);
else if(y<=m) return l->rmq(x,y,a,b);
else {
if(y - (m+1) >= m - x) {
if(!r->rmq(m+1,y,a,b)) return l->rmq(x,m,a,b);
return 1;
}else{
if(!l->rmq(x,m,a,b)) return r->rmq(m+1,y,a,b);
return 1;
}
}
}
}*solve;
ll q, p[MAXN], pos_mx[MAXN], rope[2][MAXN][2], b, pos_mi[MAXN];
vector<int> ans;
vector<pi> v[MAXN], adj[MAXN];
vector<spi> e;
bitset<MAXN> vis;
int find(int x){return p[x]==x?x:p[x]=find(p[x]);}
void merge(int x,int y,ll W){
x=find(x),y=find(y);
if(x==y)return;
adj[rope[b][x][1]].eb(rope[b][y][0],W);
adj[rope[b][y][0]].eb(rope[b][x][1],W);
rope[b][y][0]=rope[b][x][0];
p[x]=y;
}
void build_mx(){
sort(all(e), greater<spi>());
FOR(i,0,n-1)rope[b][i][0]=rope[b][i][1]=i,p[i]=i;
for(auto i:e){
merge(i.s.f,i.s.s,i.f);
}
vector<int> order;
function<void(ll,ll)>dfs=[&](ll x,ll p){
if(vis[x])return;
vis[x]=1;
order.eb(x);
for(auto i:adj[x]) if(i.f^p) cost.eb(i.s), dfs(i.f,x);
};
vis.reset(), dfs(rope[b][find(0)][0],-1), assert(siz(order)==n), assert(siz(cost)==n-1);
FOR(i,0,n-1)pos_mx[order[i]]=i;
maxi.build();
}
void build_mi(){
b=1;
sort(all(e));
FOR(i,0,n-1)rope[b][i][0]=rope[b][i][1]=i,p[i]=i;
for(auto i:e){
merge(i.s.f,i.s.s,i.f);
}
vector<int> order; cost.clear();
function<void(ll,ll)>dfs=[&](ll x,ll p){
if(vis[x])return;
vis[x]=1;
order.eb(x);
for(auto i:adj[x]) if(i.f^p) cost.eb(i.s), dfs(i.f,x);
};
vis.reset(), dfs(rope[b][find(0)][0],-1), assert(siz(order)==n), assert(siz(cost)==n-1);
FOR(i,0,n-1)pos_mi[order[i]]=i;
mini.build();
}
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, q=S.size(), ans.resize(q,0);
FOR(i,0,siz(X)-1){
v[X[i]].eb(Y[i],min(X[i],Y[i]));
v[Y[i]].eb(X[i],min(X[i],Y[i]));
e.eb(min(X[i],Y[i]),pi(X[i],Y[i]));
}
build_mx();
// change edges
FOR(i,0,n-1)v[i].clear(),adj[i].clear();
e.clear();
FOR(i,0,siz(X)-1){
v[X[i]].eb(Y[i],max(X[i],Y[i]));
v[Y[i]].eb(X[i],max(X[i],Y[i]));
e.eb(max(X[i],Y[i]),pi(X[i],Y[i]));
}
build_mi();
solve=new node2(0,n-1);
FOR(i,0,n-1)solve->update(pos_mi[i],pos_mx[i]);
solve->prog();
FOR(i,0,q-1){
ll bs[2], be[2];
ll st=-1,en=pos_mx[S[i]];
while(en-st>1){
ll mid=(st+en)>>1;
if(maxi.rmq(mid,pos_mx[S[i]]-1)>=L[i])en=mid;
else st=mid;
}
bs[0]=en;
st=pos_mx[S[i]],en=n;
while(en-st>1){
ll mid=(st+en)>>1;
if(maxi.rmq(pos_mx[S[i]],mid-1)>=L[i])st=mid;
else en=mid;
}
bs[1]=st;
st=-1,en=pos_mi[E[i]];
while(en-st>1){
ll mid=(st+en)>>1;
if(mini.rmq(mid,pos_mi[E[i]]-1)<=R[i])en=mid;
else st=mid;
}
be[0]=en;
st=pos_mi[E[i]],en=n;
while(en-st>1){
ll mid=(st+en)>>1;
if(mini.rmq(pos_mi[E[i]],mid-1)<=R[i])st=mid;
else en=mid;
}
be[1]=st;
ans[i] = solve->rmq(be[0],be[1],bs[0],bs[1]);
}
return ans;
}
