调了一个下午只有八十分QAQ md弃了不管了 对拍也没拍出来 鬼知道是什么数据把我卡了QAQ
没事我只是个SB而已 这题其实还是蛮正常的
做法其实很简单 根据链剖的构造方法 你每次修改都是一段又一段的线段
那么你只要求一下线段并起来后哪些地方被覆盖了>=t次 不过要基数排序一波不然会T
#include<cstdio> #include<cstring> #include<algorithm> #define LL long long using std::swap; using std::max; const int N=450007,M=30000000,B=1024; int read(){ int ans=0,f=1,c=getchar(); while(c<'0'||c>'9'){if(c=='-') f=-1; c=getchar();} while(c>='0'&&c<='9'){ans=ans*10+(c-'0'); c=getchar();} return ans*f; } int n,m; int first[N],cnt=1; struct node{int to,next;}e[2*N]; void ins(int a,int b){e[++cnt]=(node){b,first[a]}; first[a]=cnt;} void insert(int a,int b){ins(a,b); ins(b,a);} int dep[N],top[N],sz[N],son[N],mx[N],fa[N],id[N],idp=1; void f1(int x){ sz[x]=1; for(int i=first[x];i;i=e[i].next){ int now=e[i].to; if(now==fa[x]) continue; fa[now]=x; dep[now]=dep[x]+1; f1(now);sz[x]+=sz[now]; if(sz[now]>sz[son[x]]) son[x]=now; } } void f2(int x,int tp){ top[x]=tp; mx[x]=id[x]=idp++; if(son[x]) f2(son[x],tp),mx[x]=max(mx[x],mx[son[x]]); for(int i=first[x];i;i=e[i].next){ int now=e[i].to; if(now!=fa[x]&&now!=son[x]) f2(now,now),mx[x]=max(mx[x],mx[now]); } } bool ly; int a,b,t,cntq; int f[2*M]; struct pos{int r,id,s;}q[M]; bool cmp(pos a,pos b){return a.r<b.r;} void pcalc(){ memset(f,0,sizeof(f)); for(int i=0;i<cntq;i++) f[q[i].r]+=q[i].s; cntq=0; } void modify(int x,int y,int k){ while(top[x]!=top[y]){ if(dep[top[x]]<dep[top[y]]) swap(x,y); if(!ly){f[id[top[x]]]++; f[id[x]+1]--; x=fa[top[x]];continue;} q[cntq++]=(pos){id[top[x]],k,1}; q[cntq++]=(pos){id[x]+1,k,-1}; if(cntq>1e6&&ly){pcalc(); ly=false;} x=fa[top[x]]; } if(id[x]>id[y]) swap(x,y); if(!ly){f[id[x]]++; f[id[y]+1]--; return ;} q[cntq++]=(pos){id[x],k,1}; q[cntq++]=(pos){id[y]+1,k,-1}; } int T[1257]; pos *s[1257],*mp; pos bb[M]; void jsort(int n){ memset(T,0,sizeof(T)); mp=bb; for(int i=0;i<n;i++) ++T[q[i].r&1023]; for(int i=0;i<B;i++) s[i]=mp,mp+=T[i]; for(int i=0;i<n;i++) *s[q[i].r&1023]++=q[i]; memset(T,0,sizeof(T)); mp=q; for(int i=0;i<n;i++) ++T[bb[i].r>>10]; for(int i=0;i<B;i++) s[i]=mp,mp+=T[i]; for(int i=0;i<n;i++) *s[bb[i].r>>10]++=bb[i]; } int main(){ //freopen("gg.in","r",stdin); int x,y; n=read(); m=read(); for(int i=1;i<n;i++) x=read(),y=read(),insert(x,y); f1(1); f2(1,1); for(int i=1;i<=m;i++){ a=read(); b=read(); t=read(); cntq=0; ly=true; for(int j=1;j<=a;j++){ x=read(); y=read(); modify(x,y,i); } for(int j=1;j<=b;j++){ x=read(); if(!ly){f[id[x]]++; f[mx[x]+1]--;continue;} q[cntq++]=(pos){id[x],i,1}; q[cntq++]=(pos){mx[x]+1,i,-1}; if(cntq>1e6&&ly){pcalc(); ly=false;} } if(t==0){printf("%d ",n); continue;} if(ly){ jsort(cntq); int now=0,ans=0; for(int j=0;j<cntq;j++){ now+=q[j].s; if(j!=cntq-1&&now>=t) ans=ans+q[j+1].r-q[j].r; } if(now>=t) ans=ans+n-q[cntq-1].r+1; printf("%d ",ans); } else{ int now=0,ans=0; for(int j=1;j<=n;j++){ now+=f[j]; if(now>=t) ans++; }printf("%d ",ans); } } return 0; }