Run ID | 作者 | 问题 | 语言 | 测评结果 | 分数 | 时间 | 内存 | 代码长度 | 提交时间 |
---|---|---|---|---|---|---|---|---|---|
51833 | HyperSQ | 树上博弈 | C++ | 通过 | 100 | 517 MS | 14320 KB | 1727 | 2022-07-13 16:08:52 |
#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<<1],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); for(int j=1;j<=m;j++){ int i=id[j]; 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]); } for(int i=1;i<=m;i++){ printf("%d\n",ans[i]); } }