提交时间:2022-07-13 16:03:11
运行 ID: 51831
#include <bits/stdc++.h> using namespace std; const int maxn=1e5+5; int n,m,k; struct node{ int v,nxt,w; }edge[maxn<<1]; int head[maxn],cntE; void add(int u,int v,int w){ edge[++cntE]=(node){v,head[u],w}; head[u]=cntE; } int clk,in[maxn],out[maxn],rnk[maxn],val[maxn]; int Ql[maxn],Qr[maxn],R[maxn]; void init(int u,int p,int w){ in[u]=++clk,rnk[clk]=u; val[u]=w; for(int i=head[u];i;i=edge[i].nxt){ int v=edge[i].v,W=edge[i].w;if(v==p) continue; init(v,u,W); } out[u]=++clk,rnk[clk]=u; } bool cmp(int i,int j){ if(Ql[i]/k!=Ql[j]/k) return Ql[i]<Ql[j]; else return Qr[i]<Qr[j]; } bitset<maxn> bst; void flip(int x){ if(!x) return; bst.flip(n-x+1); } void add(int x){ flip(val[rnk[x]]); } void erase(int x){ flip(val[rnk[x]]); } int query(int x){ if(bst[n-x+1]) return 0; int y=bst._Find_next(n-x+1); if(y==maxn) y=n+1; y=n-y+1; return x-y; } int id[maxn],U[maxn],V[maxn],ans[maxn]; int main(){ scanf("%d",&n); for(int i=1;i<=n-1;i++){ int u,v,w;scanf("%d%d%d",&u,&v,&w); add(u,v,w);add(v,u,w); } init(1,1,0); scanf("%d",&m); k=n/sqrt(m); for(int i=1;i<=m;i++){ id[i]=i;scanf("%d%d%d",&U[i],&V[i],&R[i]); if(in[U[i]]>out[V[i]]||(in[V[i]]<in[U[i]]&&out[U[i]]<out[V[i]])) swap(U[i],V[i]); if(in[V[i]]>in[U[i]]&&out[U[i]]>out[V[i]]) Ql[i]=in[U[i]]+1,Qr[i]=in[V[i]]; else Ql[i]=out[U[i]],Qr[i]=in[V[i]]; } sort(id+1,id+m+1,cmp); int T=1,S=1;bst.flip(n+1); //cout<<bst<<endl; for(int j=1;j<=m;j++){ int i=id[j]; //cout<<U[i]<<" "<<V[i]<<endl; while(S<Ql[i]) erase(S++); while(S>Ql[i]) add(--S); while(T<Qr[i]) add(++T); while(T>Qr[i]) erase(T--); ans[i]=query(R[i]); //cout<<bst<<endl; //cout<<ans[i]<<endl; } for(int i=1;i<=m;i++){ printf("%d\n",ans[i]); } }