题解 P3241 【[HNOI2015]开店】

这里是常数极大的动态点分治题解 由于自己主席树不会压缩版本导致了尴尬的mle，然后就滚过去写点分树了 ## 前置芝士：动态点分治(点分树) 所谓动态点分治，实际上是一个静态的不能再静态的数据结构——点分树，甚至连数据结构都算不上，只能说是一个log级别的高级暴力，为了避免误会，以下称“动态点分治”这个算法为“点分树” 在学习动态点分治之前，请先出门左转你站模板区AC点分治的模板 你会发现所谓点分治不过是控制了下O(nlogn)暴力的次数而已，我们做了log次O(nlogn)的暴力，于是就得到了O(nlog^2n)的点分治，而点分树其实和点分治的关系不是特别密切了，二者唯一的联系就是点分树通过点分治的函数来建树而已…… 点分树的想法是这样的，有的问题我们不是非常关心树的形态特点，比如路径问题，联通块问题，寻找关键点问题等等，以路径问题为例，我们不一定非得查到p,q的lca才可以处理p，q的路径信息，相反，我们可以随便从这个路径上寻找一个分割点G,只要我们可以快速的处理p到G和q到G的信息，我们有些时候就可以处理p到q的信息 所以点分树事实上是对原树做了一种扭曲的映射，使得映射之后满足下列条件 1.原树上任意两点p,q在点分树上的lca一定在p到q的路径上 2.点分树的树高是O(logn)的 因此点分树允许我们进行下面两个在一般树上根本不可能做到的暴力 1.暴力跳father获得某一个点到根节点的路径 2.在每一个点里开一个vector，存储它的孩子的所有信息，空间复杂度是 ## $O(\sum size)=O(\sum dep)=O(nlogn)$ 然后我们就可以在点分树上开心的使用暴力了~ ## 点分树的构建 首先我们根据点分治的过程：找到当前连通块的重心，删去重心，对每个连通块递归子过程这个经典算法来对整棵树做剖分，我们删去重心g之后，从g向各个子联通的重心连边，这样就构成了一颗点分树 可以证明的是，两个点在点分树上的lca一定在原树上这两个点的路径上，但是，点分树除此之外和原树的关系十分的小，尤其是点分树具有这样一条性质， 一个点到它点分树的各个祖先的距离很可能没有任何性质，也就是说我们并不能通过跳点分树上的father的形式来访问一个点到点分树根的信息，因为我们是无法通过累加各个边上边权的方式来计算点到它的点分树祖先的距离的 因此我们存储一个点分树的方式是在一个点开一个vector上存储他到每个祖先的距离以及祖先的编号，这样我们在访问这个节点的所有祖先的时候只需要暴力的扫一遍整个vector就可以获得整个路径上的信息了 另外除了自底向上的访问过程，我们有些时候还需要处理一个点和其他子连通块之间的关系，此时我们可能需要对于每个重心暴力开一个vector处理他的所有子连通块的信息了 总之，点分树的算法思想就是因为反正我是$O(logn)$的树高，因此我可以很多时候使用一些十分暴力的手段，每个点暴力记祖先和孩子，总复杂度还是$O(nlogn)$的 ## 所以，点分树事实上是一个精心设计过的暴力 ## 本题题解 那么对于这道题来讲我们还是先想一个暴力然后把它放到点分树上去做就可以了 我们仿照一般树上询问一个点到其他所有点距离的方式(当然会有一个非常优美的树剖算法，这个暂且不谈)，我们对整棵树建一个点分树，然后每个节点使用vector记录他到各个祖先节点的距离，那么现在我们要求这个和其他点的距离了 我们想一下一般情况下lca法求树上距离的方案，事实上我们是通过lca这个“分割点”将树上的路径分成了两个我们可以快速处理的部分，即树上深度，但是事实上lca除了这个用途之外它的意义不是很大 换句话来讲，我们可以不使用lca作为分割点，而是使用一些别的点作为分割点，前提是我们必须保证分成的两部分路径我们可以快速处理，那么我们想到了两个点分数上的lca，点分树上的lca一定在这两个点的路径上，而两个点到点分树祖先的距离又可以快速处理，因此我们认为点分树上的lca是一个优秀的分割点 那么仿照一般情况下我们在树上求点p到所有点的距离的算法:枚举lca然后依次算贡献，这需要一个一个的跳链，最坏复杂度$O(n)$，然后我们如果把枚举lca换成枚举点分树的lca，复杂度就成了$O(logn)$的了 那么我们考虑我们需要预处理什么信息呢？，首先每个点开一个vector存储这个点的所有祖先和到所有祖先的距离，因为前面说过点分树上距离并不具有递推性质，所以只能暴力的存，然后每个点开另外一个vector存储所有的子联通块以及子联通块中的点到这个点的距离之和，这样的话我们就处理出了过这个点的两边路径信息了 好了我们现在要询问点p到树上所有点的距离之和了，让我们来简单的描述下算法流程 1.使用点分治算法处理出点分树，然后使用vector存储下刚才的信息 2.暴力的扫一遍点p的祖先vector，对于每一个祖先g，答案+=p到g的距离+p到g的距离×g的不包含p的子联通块siz和+g的不包含p的子联通块中的点到g的距离之和 如果不理解的话可以自己画个图了解一下 好了我们发现刚才算法的关键在于如何求出“g的不包含p的子联通块siz和”以及“g的不包含p的子联通块中的点到g的距离之和”这两个信息 方法1，可以存储和，然后减去p的信息，(这里务必注意不能用g的和减去p的和，仔细回想一下会发现点分树的父子关系其实很弱，所以这两个信息根本没有关系也不能减，必须在g下单独存储每一个子联通块到g的信息) 方法2，如果点度数很小，我们可以暴力扫一遍g的孩子vector，然后跳过含p的子联通块即可，注意如果点的度数在20左右，你的算法复杂度很可能和两个log没啥区别 _____________________ 好了我们现在唯一要做的就是给刚才的做法加上点权限制，每个点暴力记录到祖先的距离当然是省不了的，但是我们该如何处理g的子联通块信息呢？ 当然你可以把vector换成权值线段树，配合动态开点，空间复杂度应该还是可以控制在一个log上，但是又没有修改干嘛开线段树呢？不嫌烦吗？ 所以我们采取一些更加暴力的手段，我们每个点上开3个vector，每个vector存储这个子联通块里的所有点的点权和深度，冷静分析一波会发现这个看似暴力的做法空间复杂度只有$O(nlogn)$ 然后把每个vector按点权排序之后处理siz的后缀和和dep的后缀和，在执行刚才算法的时候每枚举一个祖先g就处理一下它的3个vector，不算p的那个vector，然后我们在这个vector上二分出所有合法的点的区间，然后两个后缀和直接相减就可以得出不含p且值域符合要求的点的siz以及不含p且值域符合要求的点的dep之和了 另外为什么是后缀和而不是前缀和？，你会发现前缀和支持的是左开右闭区间，但是我们使用upper\_bound和lower\_bound二分出这左开右闭的区间是十分困难的(需要加一减一之类的还得小心迭代器失效)，相比之下我们二分出左闭右开的区间会容易许多，因此我们就使用后缀和了 说了这么多，其实点分治还是相当小清新的数据结构，代码难度相对树剖+主席树的做法也会小很多……比如这题我大概才写了70行 上代码~ ```C // luogu-judger-enable-o2 #include<cstdio> #include<algorithm> #include<vector> using namespace std;const int N=15*1e4+10;typedef long long ll; int v[2*N];int x[2*N];int ct;int al[N];int val[2*N];bool book[N];bool cut[N]; int siz[N];int w[N];ll dep[N];int tot;int nrt;int miv;ll res;int n;int m;ll A; struct data//存储节点信息的vector { int val;ll ss;ll sv; friend bool operator <(data a,data b){return a.val<b.val;} };vector <data> ans[N][3]; struct ed{int f;ll dis;int tp;};vector <ed> fa[N];//存储到祖先距离的vector inline void add(int u,int V,int va){v[++ct]=V;x[ct]=al[u];al[u]=ct;val[ct]=va;} void dfs1(int u)//寻找siz { book[u]=true;siz[u]=1; for(int i=al[u];i;i=x[i]){if(!book[v[i]]&&!cut[v[i]]){dfs1(v[i]);siz[u]+=siz[v[i]];}} book[u]=false; } void dfs2(int u)//寻找中心 { book[u]=true;int mav=tot-siz[u]; for(int i=al[u];i;i=x[i]){if(!book[v[i]]&&!cut[v[i]]){dfs2(v[i]);mav=max(mav,siz[v[i]]);}} book[u]=false;if(miv>mav){miv=mav;nrt=u;} } void dfs3(int u,const int& g,const int& t)//处理深度 { book[u]=true;fa[u].push_back((ed){g,dep[u],t}); ans[g][t].push_back((data){w[u],1,dep[u]}); for(int i=al[u];i;i=x[i]){if(!book[v[i]]&&!cut[v[i]]){dep[v[i]]=dep[u]+val[i];dfs3(v[i],g,t);}} book[u]=false; } void solve(int u)//点分治构建点分树 { dfs1(u);if(siz[u]==1){cut[u]=true;fa[u].push_back((ed){u,0,-1});return;}//边界条件 tot=siz[u];miv=0x3f3f3f3f;dfs2(u);cut[nrt]=true;fa[nrt].push_back((ed){nrt,0,-1}); for(int i=al[nrt],t=0;i;i=x[i]) { if(cut[v[i]]){continue;} dep[v[i]]=val[i];dfs3(v[i],nrt,t);//预处理vector ans[nrt][t].push_back((data){0x3f3f3f3f,0,0}); sort(ans[nrt][t].begin(),ans[nrt][t].end());//按点权sort for(int j=ans[nrt][t].size()-2;j>=0;j--) { ans[nrt][t][j].ss+=ans[nrt][t][j+1].ss;//处理后缀和 ans[nrt][t][j].sv+=ans[nrt][t][j+1].sv; }t++; }for(int i=al[nrt];i;i=x[i]){if(!cut[v[i]]){solve(v[i]);}}//递归点分治 } inline void query(int l,int r,int u)//暴力跳链，二分出答案 { res=0;vector <data>:: iterator L;vector <data>:: iterator R; for(int i=fa[u].size()-1;i>=0;i--) { int f=fa[u][i].f; for(int tp=0;tp<=2;tp++) { if(tp==fa[u][i].tp||ans[f][tp].empty()){continue;} L=lower_bound(ans[f][tp].begin(),ans[f][tp].end(),(data){l,0,0});//使用upper和lower_bound可以轻易的二分出一个左闭右开的边界 R=upper_bound(ans[f][tp].begin(),ans[f][tp].end(),(data){r,0,0}); res+=fa[u][i].dis*(L->ss-R->ss)+L->sv-R->sv;//处理这个重心的贡献 }if(l<=w[f]&&w[f]<=r){res+=fa[u][i].dis;}//特判一下这个点到中心的距离 } } int main() { scanf("%d%d%lld",&n,&m,&A); for(int i=1;i<=n;i++){scanf("%d",&w[i]);} for(int i=1,u,v,c;i<n;i++){scanf("%d%d%d",&u,&v,&c);add(u,v,c);add(v,u,c);} solve(1);//点分治 for(int i=1;i<=m;i++) { int u;ll l;ll r;scanf("%d%lld%lld",&u,&l,&r); (l+=res)%=A;(r+=res)%=A;if(l>r)swap(l,r); query(l,r,u);printf("%lld\n",res);//处理答案 }return 0;//拜拜程序~ } ```