#include using namespace std; int n,m,ans[500010]; vectorG[500010]; namespace pre{ struct N_{int l,r,d;}; vectorseg; int fa[500010][21],dfn[500010],out[500010],tot,dep[500010]; void dfs(int u){ dfn[u]=++tot; dep[u]=dep[fa[u][0]]+1; for(int i=1;i<=20;i++)fa[u][i]=fa[fa[u][i-1]][i-1]; for(int v:G[u])if(v!=fa[u][0]){ fa[v][0]=u,dfs(v); } out[u]=++tot; } int stk[1000010],L[500010],tp; inline int lca(int u,int v){ if(dep[u]=0;i--)if(dep[fa[u][i]]>=dep[v])u=fa[u][i]; if(u==v)return u; for(int i=20;i>=0;i--)if(fa[u][i]!=fa[v][i]){ u=fa[u][i],v=fa[v][i]; } return fa[u][0]; } inline bool isanc(int u,int anc){ return dfn[anc]<=dfn[u]&&out[u]<=out[anc]; } void init(){ dfs(1); for(int i=1;i<=n;i++){ for(;tp&&!isanc(i,stk[tp]);tp--)seg.push_back({L[tp-1]+1,i-1,dep[stk[tp]]}); if(i>1)tp++,stk[tp]=lca(i-1,i),L[tp]=i-1; tp++,stk[tp]=i,L[tp]=i; } for(int i=1;i<=tp;i++)seg.push_back({L[i-1]+1,n,dep[stk[i]]}); } } namespace ds1{ struct Q_{int l,r,i;}; struct N_{int y,v;}; vectorq[500010]; vectorpnts[500010]; int mx[500010<<2]; int qry(int u,int l,int r,int L,int R){ if(L<=l&&r<=R)return mx[u]; int mid=l+r>>1; return max(L<=mid?qry(u<<1,l,mid,L,R):0,R>mid?qry(u<<1|1,mid+1,r,L,R):0); } void ins(int u,int l,int r,int p,int v){ mx[u]=max(mx[u],v); if(l==r)return; int mid=l+r>>1; if(p<=mid)ins(u<<1,l,mid,p,v); else ins(u<<1|1,mid+1,r,p,v); } void solve(){ for(int i=1;i<=n;i++){ for(N_ x:pnts[i])ins(1,1,n,x.y,x.v); for(Q_ x:q[i])ans[x.i]=max(ans[x.i],qry(1,1,n,x.l,x.r)); } memset(mx,0,sizeof(mx)); for(int i=1;i<=n;i++)pnts[i].clear(),q[i].clear(); } } struct Q_{int l,r,k;}q[500010]; int main(){ freopen("query.in","r",stdin); freopen("query.out","w",stdout); scanf("%d",&n); for(int i=1,u,v;i