题解 【P6778 [Ynoi2009] rpdq】

本题解无 $\text{top cluster}$ 树分块，请放心食用。（迫真） - 前置芝士 - 二次离线莫队 ： [P5047 [Ynoi2019 模拟赛] Yuno loves sqrt technology II](https://www.luogu.com.cn/problem/P5047) - 经典问题 ： [P4211 [LNOI2014]LCA](https://www.luogu.com.cn/problem/P4211) ------------ **题意** ： 给定一棵 $n$ 个点的树，边有边权。 每次询问给出 $l,r$ ，求 ： $$\sum\limits_{l\leq u<v\leq r}dis(u,v)$$ 答案对 $2^{32}$ 取模。 允许离线， $n,q\leq 2\times 10^5$ ，时限$\texttt{4s}$ ，空限$\texttt{1Gb}$。 ------------ 使用**二次离线莫队**。 容易将问题转化为 $O(n\sqrt{m})$ 次 $$ \begin{aligned} &\sum\limits_{v\leq r}dis(u,v)\\ =&r\times dep_u+\sum\limits_{v\leq r}dep_v-2\sum\limits_{v\leq r}dep_{{\rm lca}(u,v)} \end{aligned} $$ 的求解。 难点在于 $\sum\limits_{v\leq r}dep_{{\rm lca}(u,v)}$ ，这是 “经典问题” ，将点 $1\sim r$ 到根的点权加上父边边权，然后查询 $u$ 到根的路径和即可得到。 问题转化为 $O(n)$ 次路径加与 $O(n\sqrt{m})$ 次路径求和。 然后我们尴尬地发现，常用的树上数据结构几乎全部带 $\log$ ，不能很好地平衡复杂度。 考虑**树分块**。 每个点只归属于一个块，每个块形成一个树上联通块。**记块中的最浅点为关键点。** 接下来是分块方法。 若 $siz_u\leq \sqrt{n}$ 且 $siz_{fa}>\sqrt{n}$ ，则将 $u$ 的子树分成一块。（第一类） 这样还剩了所有子树大小 $>\sqrt{n}$ 的点没有归属，这些点构成一棵分叉为 $O(\sqrt{n})$ 的树。 对于每条**不分叉**的链条，尽量按照 $\sqrt{n}$ 划分，如果最后剩下一小段不足 $\sqrt{n}$ ，也直接分成一块。（第二类）  第二类块的个数为 $O(\sqrt{n})$ ，形态为**一条链**。 第一类块的个数不限，形态为一棵子树。一类块下面不再有块，一类块上面一定是二类块。 记 $f_u$ 为 $u$ 的父亲， $b_u$ 为 $u$ 所在块的关键点。 - 对 $u$ 进行链加 记 $w_u$ 表示 $u$ 到关键点的路径的和。 若 $u$ 在一类块中，暴力 $\rm dfs$ 整块更新 $w$ ，然后修改 $f_{b_u}$ ，则转化为 $u$ 在二类块中的情况。 若 $u$ 在二类块中，仍然先暴力 $\rm dfs$ 整块更新 $w$ 。 $u$ 还会对祖先块的 $w$ 进行贡献。注意到由于二类块形态是一条链，一定是整个块都加，只需要记下整块标记。 对于**二类块**的关键点，维护到根的路径的和，由于二类块的个数较少，可以每次修改后暴力 $\rm dfs$ 计算。 - 对 $u$ 进行链查询 若 $u$ 在一类块中，答案加上 $w_u$ ，然后查询 $f_{b_u}$ ，则转化为 $u$ 在二类块中的情况。 若 $u$ 在二类块中，答案为 $tag_{b_u}\times td_u+w_u+w'_{b_u}$ 其中 $tag_{b_u}$ 表示块 $b_u$ 被整体加的次数， $td_u$ 表示 $u$ 到关键点的距离， $w'_{b_u}$ 表示关键点 $b_u$ 到根的路径和。 时间复杂度 $O\big(n(\sqrt{n}+\sqrt{m})\big)$ ，空间复杂度 $O(n)$。 常数不大，最慢点 $\rm 2.2s$。 ```cpp #include<algorithm> #include<cstring> #include<cstdio> #include<vector> #include<cmath> #define uint unsigned int #define pb emplace_back #define MaxN 200500 using namespace std; namespace io {}using namespace io; vector<int> g[MaxN],p[MaxN]; vector<uint> l[MaxN]; int siz[MaxN],fa[MaxN],tf[MaxN] ,f2[MaxN],p2[1050],tn,stk[MaxN],top,BS2; uint dis[MaxN],lf[MaxN],td[MaxN],sd[MaxN]; void pfs(int u) { siz[u]=1; for (int i=0,v;i<g[u].size();i++) if (!siz[v=g[u][i]]){ dis[v]=dis[fa[v]=u]+(lf[v]=l[u][i]); pfs(v); siz[u]+=siz[v]; } } void pfs2(int u) { int sav=top; for (int i=0;i<g[u].size();i++) if (siz[u]>siz[g[u][i]])pfs2(g[u][i]); stk[++top]=u; if (u==1||top-sav>=BS2||siz[u]<=BS2&&siz[fa[u]]>BS2||siz[fa[u]]-siz[u]>BS2) while(top>sav)tf[stk[top--]]=u; } bool cmpP(int A,int B){return dis[A]<dis[B];} uint val[MaxN],tag[MaxN],w[MaxN],w2[MaxN],sum[MaxN]; void add(int u) { int t=tf[u]; for (int p=u;p!=t;p=fa[p])val[p]+=lf[p]; val[t]+=lf[t];w[t]=val[t]; for (int i=1;i<p[t].size();i++){ int v=p[t][i]; w[v]=w[fa[v]]+val[v]; } if (siz[t]<BS2)add(fa[t]); else { sum[t]+=td[u]; for (int p=t;f2[p];p=f2[p]){ tag[f2[p]]++; sum[f2[p]]+=td[fa[p]]; } for (int i=2;i<=tn;i++){ int v=p2[i]; w2[v]=w2[f2[v]]+sum[f2[v]]; } } } inline uint qry(int u) {return siz[tf[u]]<BS2 ? w[u]+qry(fa[tf[u]]) : w[u]+w2[tf[u]]+tag[tf[u]]*td[u];} struct Data{int l,r,p;}; vector<Data> bl[MaxN],br[MaxN]; Data b[MaxN];int BS; bool cmpQ(const Data &A,const Data &B) {return A.l/BS==B.l/BS ? (A.l/BS)&1 ? A.r<B.r : A.r>B.r : A.l<B.l;} uint sav[MaxN],ans[MaxN]; int n,m; int main() { n=rd();m=rd(); BS2=min((int)(sqrt(n)+5),n); BS=0.75*n/sqrt(m)+5; for (int i=1;i<n;i++){ int u=rd(),v=rd();uint len=rd(); g[u].pb(v);l[u].pb(len); g[v].pb(u);l[v].pb(len); } for (int i=1;i<=m;i++) {b[i].l=rd();b[i].r=rd();b[i].p=i;} sort(b+1,b+m+1,cmpQ); pfs(1);pfs2(1); for (int i=1;i<=n;i++){ sd[i]=sd[i-1]+dis[i]; td[i]=dis[i]-dis[fa[tf[i]]]; p[tf[i]].pb(i); } p2[tn=1]=1; sort(p[1].begin(),p[1].end(),cmpP); for (int u=2;u<=n;u++)if (tf[u]==u){ sort(p[u].begin(),p[u].end(),cmpP); if (siz[u]>=BS2)p2[++tn]=u; int v=fa[u];while(tf[v]!=v)v=fa[v]; f2[u]=v; }sort(p2+1,p2+tn+1,cmpP); for (int i=1,l=1,r=0;i<=m;i++){ if (b[i].l<l){bl[r].pb((Data){b[i].l,l-1,b[i].p});l=b[i].l;} if (r<b[i].r){br[l].pb((Data){r+1,b[i].r,b[i].p});r=b[i].r;} if (l<b[i].l){bl[r].pb((Data){l,b[i].l-1,-b[i].p});l=b[i].l;} if (b[i].r<r){br[l].pb((Data){b[i].r+1,r,-b[i].p});r=b[i].r;} } #define ad(p,x) if (p<0)ans[-p]-=x;else ans[p]+=x; for (int i=1;i<=n;i++){ for (int j=0;j<br[i].size();j++){ Data &now=br[i][j];uint ret=0; for (int r=now.l;r<=now.r;r++) ret+=(uint)(r-i)*dis[r]+(sd[r-1]-sd[i-1])-2u*(-qry(r)); ad(now.p,ret); } add(i);sav[i]=qry(i); for (int j=0;j<bl[i].size();j++){ Data &now=bl[i][j];uint ret=0; for (int l=now.l;l<=now.r;l++) ret+=(uint)(i-l)*dis[l]+(sd[i]-sd[l])-2u*(qry(l)-sav[l]); ad(now.p,ret); } } for (int i=1;i<=n;i++) for (int j=0;j<br[i].size();j++){ Data &now=br[i][j];uint ret=0; for (int r=now.l;r<=now.r;r++)ret-=2u*(sav[r]-dis[r]); ad(now.p,ret); } for (int i=1;i<=m;i++)ans[b[i].p]+=ans[b[i-1].p]; for (int i=1;i<=m;i++)print(ans[i]),putc('\n'); flush(); return 0; } ```