#include #include #include using namespace std; int read(){ int re=0,c=getchar(); while(c<'0'||c>'9') c=getchar(); while(c>='0'&&c<='9') re=(re<<3)+(re<<1)+(c^48),c=getchar(); return re; } void write(int w){ int c[20],pos=0; while(w) c[++pos]=w%10^48,w/=10; for (int i=pos;i;i--) putchar(c[i]); putchar('\n'); } const int maxn=5e5+5; struct L{ int v,bro; }li[maxn*2]; struct Q{ int l,r,k,mo,id; }qs[maxn*4],qy[maxn],ds[maxn],tq[maxn*4]; int n,head[maxn],cnt,q,dep[maxn],lp[maxn],ld[maxn],lg[maxn],pt[maxn][25]; int dfn[maxn],cntd,sz[maxn],da[maxn][25],di[maxn][25],dpm[maxn][25],cx[maxn]; int cq,cd,ans[maxn],qa[maxn]; vector px[maxn]; void add(int u,int v){ li[++cnt]=(L){v,head[u]},head[u]=cnt; } void dfsi(int u,int pr){ pt[u][0]=pr,sz[u]=1,dfn[u]=++cntd; for (int i=1;i<=lg[dep[u]];i++) pt[u][i]=pt[pt[u][i-1]][i-1]; for (int i=head[u];i;i=li[i].bro){ int v=li[i].v; if(v==pr) continue; dep[v]=dep[u]+1,dfsi(v,u),sz[u]+=sz[v]; } } int lca(int u,int v){ if(dep[u]dep[v]) u=pt[u][lg[dep[u]-dep[v]]]; if(u==v) return v; for (int i=lg[dep[u]];i>=0;i--) if(pt[u][i]!=pt[v][i]) u=pt[u][i],v=pt[v][i]; return pt[u][0]; } bool cmp(Q x,Q y){ if(x.k!=y.k) return x.k>1,vl=l,vr=mid+1,pr=l; while(vl<=mid&&vr<=r) tq[pr++]=qs[vl].l>=qs[vr].l?qs[vl++]:qs[vr++]; while(vl<=mid) tq[pr++]=qs[vl++]; while(vr<=r) tq[pr++]=qs[vr++]; for (int i=l;i<=r;i++) qs[i]=tq[i]; } int lowb(int x){return x&(-x);} void upd(int p,int v){ while(p<=n) qa[p]=max(qa[p],v),p+=lowb(p); } int qr(int r){ int re=0; while(r) re=max(re,qa[r]),r-=lowb(r); return re; } void clr(int p){ while(p<=n) qa[p]=0,p+=lowb(p); } void solve(int l,int r){ if(l==r) return; int mid=(l+r)>>1,fl=0,fr=0; solve(l,mid),solve(mid+1,r); for (int i=l;i<=mid;i++) if(qs[i].mo==1) fl=1; for (int i=mid+1;i<=r;i++) if(qs[i].mo==2) fr=1; mgs(l,mid),mgs(mid+1,r); if(!fl||!fr) return; int vr=mid+1; for (int i=l;i<=mid;i++) { if(qs[i].mo==2) continue; while(vr<=r&&qs[vr].l>=qs[i].l) { if(qs[vr].mo==2) upd(qs[vr].r,qs[vr].id); vr++; } ans[qs[i].id]=max(ans[qs[i].id],qr(qs[i].r)); } for (int i=mid+1;i<=r;i++) if(qs[i].mo==2) clr(qs[i].r); } bool cmpr(Q x,Q y){ if(x.r!=y.r) return x.r>y.r; return x.mo>y.mo; } int qrm(int l,int r){ int lv=lg[r-l+1],st=r-(1<>1]+1; } q=read(); for (int i=1;i<=q;i++){ qy[i].l=read(),qy[i].r=read(),qy[i].k=read(); qy[i].id=i,qy[i].mo=1; } dfsi(1,0); for (int i=1;i>1; if(qri(mid,p)>=dfn[u]&&qra(mid,p)>1; if(qri(p+1,mid)>=dfn[u]&&qra(p+1,mid)