题解 P6782 【[Ynoi2008]rplexq】

 思路清晰，但是难写得和个鬼一样。~~可能是我码力太差了吧~~ 观察题面，我们平时求这种答案得用DP求，所以应该不好用正常的方法直接算。 但是对于新增或删除一个点的贡献好像是可以计算的，于是我们可以用莫队算法，每次更新点时$ O(dep_x) $更新即可，复杂度是相当优越的 $O(n^2\sqrt{n})$ 。不难发现这是一个点到根的路径，所以考虑用重链剖分优化，这样我们就可以直接计算轻边的贡献了，但是对于重子树的答案依然很难求。 回顾DP的方式，对于一个节点 $x$ 的所有儿子 $v_{1\dots k}$，答案就是 $\sum\limits_{i=1}^n sum_{i-1}\times siz_{v_i}$ ，其中 $sum$ 表示儿子子树大小的前缀和。也就是我们可以钦定 $x$ 的重儿子是最后一个儿子（即最后处理），莫队时只维护轻儿子的子树大小之和以及答案，最后查重儿子只需要二维数点后计算贡献即可。这样我们的复杂度就优化到 $O(n\sqrt{n}\log n)$了。 然后去看看数据范围，2e5，1s，显然过不了。 接下来就要来点阴间优化了。 我们发现目前莫队和二维数点的复杂度分别是 $O(n\sqrt{n}\log n)$ 和 $O(n\log n)$，这显然不是lxl想要的，所以我们考虑能不能对于轻子树的修改再少一点，二维数点计算多一点点，于是就多存几个重儿子试试看。如果存 $k$ 个重儿子，那么莫队复杂度就是$O(n\sqrt{n}log_k n)$，由于查询很多，所以我们数点的数据结构应该换成 $O(\sqrt{n})$ 修改，$O(1)$ 查询的分块，所以数点复杂度是$O(n\sqrt{n}+qk)$，不难发现 $k={n}^d(d\in(0,0.5])$ 时整体复杂度就变成了 $O(n\sqrt{n})$ 。这个 $d$ 显然要根据代码常数来决定。 想到这里，我心潮澎湃地码了起来，然后获得了21分的好成绩！ 这是我的最初代码： ```cpp #include<bits/stdc++.h> using namespace std; #define int long long int read(){ int a=0;char c=getchar(); while(c>'9'||c<'0')c=getchar(); while('0'<=c&&c<='9'){ a=a*10+c-48; c=getchar(); } return a; } #define MN 200005 int n,m,rt,blk; struct data{ int l,r,x,id; }q[MN]; bool CMP(data a,data b){ if(a.l/blk==b.l/blk)return a.r<b.r; return a.l<b.l; } int fa[MN],siz[MN],top[MN],id[MN],cnt; vector<int>w[MN],edge[MN]; bool cmp(int a,int b){return siz[a]>siz[b];} void dfs(int x){ siz[x]=1; for(int i=0;i<edge[x].size();++i){ int v=edge[x][i]; if(fa[x]==v)continue; fa[v]=x; dfs(v); siz[x]+=siz[v]; } sort(edge[x].begin(),edge[x].end(),cmp); int N=min(blk,(int)edge[x].size()); for(int i=0;i<N;++i){ int v=edge[x][i]; if(fa[x]==v)continue; w[x].push_back(v); } } void DFS(int x){ id[x]=++cnt; // cerr<<"DFS: "<<x<<" "<<cnt<<endl; int N=min(blk,(int)edge[x].size()); for(int i=0;i<N;++i){ int v=edge[x][i]; if(fa[x]==v)continue; top[v]=top[x]; DFS(v); } for(int i=N;i<edge[x].size();++i){ int v=edge[x][i]; if(fa[x]==v)continue; top[v]=v; DFS(v); } } //lt:轻的 //SIZ:顶端的子树大小 int ltans[MN],ltsiz[MN],SIZ[MN],_siz[MN],ans[MN],T; vector<int>tag[MN]; void upd(int x,int op){ if(op==1)ltans[x]+=ltsiz[x]*op; else ltans[x]-=ltsiz[x]-1; ltsiz[x]+=op; // cerr<<"?? "<<x<<" "<<ltsiz[x]<<endl; while(x){ int p=fa[top[x]]; if(p){ ltans[p]+=(ltsiz[p]-SIZ[top[x]])*op; ltsiz[p]+=op; // cerr<<"?upp: "<<x<<" "<<p<<" "<<ltsiz[p]<<endl; // if(p==10)cerr<<"FK!: "<<w[p].size()<<" "<<w[p][0]<<" "<<top[x]<<endl; } SIZ[top[x]]+=op; x=p; } } int a[MN],pre[MN],suf[MN],sum[1005]; vector<int>FKLXL[MN]; int loc(int x){return (x-1)/blk+1;} void ins(int x,int v){ a[x]+=v; int pos=loc(x),l=(pos-1)*blk+1,r=min(pos*blk,n); for(int i=pos;i<=blk;++i)sum[i]+=v; for(int i=x;i<=r;++i)pre[i]+=v; for(int i=x;i>=l;--i)suf[i]+=v; } int qry(int l,int r){ // cerr<<"FK: "<<l<<" "<<r<<endl; int pl=loc(l),pr=loc(r); int res=0; if(pl<pr)res=sum[pr-1]-sum[pl]; else return pre[r]-pre[l]+a[l]; return res+suf[l]+pre[r]; } signed main(){ n=read();m=read();rt=read(); blk=sqrt(n)+1; for(int i=1;i<n;++i){ int u=read(),v=read(); edge[u].push_back(v); edge[v].push_back(u); } dfs(rt);top[rt]=rt;DFS(rt); for(int i=1;i<=m;++i){ q[i].l=read(),q[i].r=read(),q[i].x=read();q[i].id=i; } sort(q+1,q+1+m,CMP); for(int i=1;i<=m;++i){ tag[q[i].l-1].push_back(i); tag[q[i].r].push_back(i); } int l=1,r=0; for(int i=1;i<=m;++i){ while(q[i].l<l)upd(--l,1); while(r<q[i].r)upd(++r,1); while(q[i].l>l)upd(l++,-1); while(r>q[i].r)upd(r--,-1); // cerr<<"FK: "<<q[i].x<<" "<<l<<" "<<r<<": "<<ans[q[i].id]<<endl; ans[q[i].id]=ltans[q[i].x]; _siz[q[i].id]=ltsiz[q[i].x]; // cerr<<"OHH "<<q[i].id<<" x:"<<q[i].x<<" "<<ltsiz[q[i].x]<<" lr:"<<l<<" "<<r<<endl; // assert(!ltans[q[i].x]); } for(int i=1;i<=n;++i){ ins(id[i],1); for(int j=0;j<tag[i].size();++j){ int ii=tag[i][j],I=q[tag[i][j]].id,x=q[ii].x; // cerr<<"qwq "<<i<<" "<<I<<" sz: "<<_siz[I]<<" "<<x<<endl; int a=0,s=_siz[I]; for(int k=0;k<w[x].size();++k){ int v=w[x][k],cnt=qry(id[w[x][k]],id[w[x][k]]+siz[w[x][k]]-1); // if(x==4)cerr<<"wdnmd: "<<w[x][k]<<" "<<cnt<<" "<<s<<endl; assert(cnt>=0); if(i==q[ii].l-1){ FKLXL[ii].push_back(cnt); } else{ // cerr<<"?? "<<FKLXL[ii].size()<<" "<<k<<endl; if(FKLXL[ii].size())cnt-=FKLXL[ii][k]; a+=s*cnt; s+=cnt; } } if(i==q[ii].l-1){ // ans[I]-=a; // cerr<<i<<" de "<<I<<" "<<a<<endl; } else { // cerr<<"FK: "<<I<<" "<<i<<" "<<q[ii].l<<" "<<q[ii].r<<endl; assert(i==q[ii].r); ans[I]+=a; // cerr<<i<<" ad "<<I<<" "<<a<<endl; } } } for(int i=1;i<=m;++i)printf("%lld\n",ans[i]); return 0; } ``` ~~你竟然不精细实现就想过Ynoi题？~~ 而且还有一个问题：查询时一共有 $n\sqrt{n}$ 次查询子树，而且此题要差分来获取子树的具体大小（答案无法差分）所以正常写空间是 $O(n\sqrt{n})$ 的。 只好请教毒瘤本人，发现他的写法是枚举```dfn```序，然后我就yy了个空间复杂度 $O(n)$ 的做法： 考虑重儿子的子树区间```dfn```序连续，也就是我这次的询问等于下次要减去的值，这样的话只要记录每次查询时上次求的值是多少即可。那么我怎么确定我要在```dfn```序为 $i$ 时回答哪些查询呢？我们记录 $i$ 为哪些节点子树```dfn```序的最后一个点，**回答关于这些节点的父亲的查询**，这样的话我们只需要在询问的 $x$ 上打标记即可。 然后卡亿点点常就可以通过本题了。卡常时注意不要在非瓶颈处浪费过多时间。 最终代码可以私戳我（但是好像交10次只能过1次），在我退役之前每天都会在线的。