【学习笔记】树论—点分树（动态点分治）

辰星凌

2020-05-27 21:54:08

Algo. & Theory

【学习笔记】树论—点分树（动态点分治）

\mathcal{My}\ \mathcal{Blog}

【前言】

~~氡态淀粉质 / 垫粪鼠~~

点分治是一种树上分治算法，常用以处理树上路径相关信息的统计。在点分治的基础上加以变化，构造一颗支持快速修改的重构树，就成了点分树。

虽说名字里带个动态，但也有人认为它应该算作静态数据结构。

（据教练所说，点分树是近几年的新兴热门考点...于是就有了这篇总结...）

一：【算法理解及复杂度分析】

前置芝士：需要有良好的 点分治 基础。

点分治的核心思想在于依据重心划分子连通块，其良好的性质保证了最多只会分治 \log n 层。有了这一特性，便可使用各种暴力计算答案。

那么我们按照分治递归的顺序提一颗新树出来，易知树高是 O(\log n) 的。

具体地说，对于每一个找到的重心，将上一层分治时的重心设为它的父亲，得到一颗大小不变、最多 \log n 层的虚树（或者理解为重构树。亦可称点分树，意义一样）。

在这颗虚树上，奇妙的性质产生了：虚树上所有点的子树大小之和为 O(n\log n) 。

证明很简单：每个点会被从根到它的路径上最多 \log n 个祖先所统计，因此总复杂度为 \sum_{i=1}^{n}depth(i)=O(n\log n) 。

如果要对某个点进行修改操作，直接在虚树上暴力跳父亲，改变 O(\log n) 个祖先的虚子树信息即可。

Q: 虚子树的信息与原树有啥关系呢？
A: 点 x 在虚树上的子树集合就是原树中以 x 为重心（分治中心）时所囊括到的连通块。
如下图（黑边为原树，灰边为虚树，蓝色编号为分治的顺序）：

以 1 为重心做分治时，所囊括的连通块为 \{1,2,3,4,5,6,7,8,9,10\}，删去该点后被划分为了 \{2,3,4,5,6\},\{7,8,9,10,11\} 两个子连通块；
以 2 为重心做分治时，所囊括的连通块为 \{2,3,4,5,6\}，删去该点后被划分为了 \{3,4\},\{5\},\{6\} 三个子连通块；
以 7 为重心做分治时，所囊括的连通块为 \{7,8,9,10,11\}，删去该点后被划分为了 \{8,9\},\{10,11\} 两个子连通块；
......

那么能用它求什么呢？

比如我们要统计某个点 x 到其他所有点的距离之和，即 \sum_{y=1}^{n}dis(x,y) 。对于任意一个 y，首先在虚树上找到它与 x 的 lca（或者说囊括连通块同时包含 x,y 的所有虚树节点中深度最深的那一个），易知在以此点为重心划分子连通块时 x,y 会首次被分割开来，因此该点必定在原树的 x,y 路径上。

所以我们只需要在这些 lca 的虚子树中寻找 y 即可，此时记录虚子树信息的作用便显现出来了。

而对于一个 x，可能的 lca 最多存在 \log n 个，因此通常使用暴力枚举+简单容斥的方法来统计 y 的贡献。具体见下文 【计算贡献】。

二：【算法实现】

【模板】点分树 / 震波 \text{[P6329]} \text{[Bzoj3730]}

【题目大意】 维护一颗带点权树，需要支持两种操作：修改 x 的点权，查询与点 x 距离不超过 K 的点权值之和。

1.【建点分树】

找到第一个重心 rt 后，先遍历整颗树得到 rt 的子树信息，然后删去 rt，得到若干个连通块（rt 的不同子树）。分别找到这些子树里的重心（在虚树上使其成为 rt 的儿子），然后递归处理这些子连通块。

实际上大体和淀粉质是相同的，只是将淀粉质中“计算答案”的操作改为了“统计虚子树信息”。

2.【计算贡献】

以下用 fa_i 表示点 i 在虚树上的父亲，subtree(i) 为点 i 在虚树上的子树集合，fatree(i) 为点 i 在虚树上的祖先集合，dis(i,j) 为 i,j 两点在原树上的距离，A_i 为点 i 的点权。

设：

为了除去某一个虚儿子子树的贡献，还需要： $f_2(i,j)=\sum_{x\in subtree(i),dis(x,fa_i)\leqslant j}A_x$，即虚树上 $i$ 的子树中与 $fa_i$ 距离小于等于 $j$ 的点权值之和。在一次查询 $(x,k)$ 中，对于虚树上的一对父子节点 $(i,fa_i)$，$subtree(fa_i)-subtree(i)$ 对答案的贡献为 $G(i,fa_i)=f_1(fa_i,k-dis(x,fa_i))$ $-$ $f_2(i,k-dis(x,fa_i))$ 。则有 $ans(x,k)=f_1(x,k)+$ $\sum_{i\in fatree(x),fa_i\neq 0} G(i,fa_i)$，注意前面那个 $f_1(x,k)$ 是因为容斥求和后 $subtree(x)$ 没有被统计进去，所以要单独拿出来算。修改点权时同理，把所有对于 $f_1,f_2$ 的查询操作换成修改就可以了。 ### **3.【维护信息】** 计算 $dis$ 可以用树剖求 $\text{LCA}$ 在线查询。也可以用欧拉序 + $\text{ST}$ 表。或者用在每次找完根后，$dfs$ 遍历一下子树预处理 $dis$ 数组。两者都是花费 $O(n\log n)$ 的时间省下了 $O(q\log^2 n)$ 的时间，但经实际测试，$\text{ST}$ 表被树剖吊起来锤，预处理与树剖不相上下，emm...过于柯怕![](https://cdn.luogu.com.cn/upload/image_hosting/9k7nlc79.png) 维护 $f_1,f_2$ 可以对每个节点开一棵动态开点线段树，下标为 $dis$（即 $f_1,f_2$ 的第二维）。时间复杂度为 $O(n\log^2 n)$，空间按照 $dis$ 范围的上界压缩一下可以做到 $O(n\log n)$（如果偷懒统一使用同一个上界 $[0,n]$ 可能会达到 $O(n\log^2 n)$）。但线段树常数略大，可能会被卡（~~虽然我过了~~），换成树状数组会稳一点。 >Q: 树状数组咋动态开点啊？ A: 当然是用动态分配内存的 $vector$ 啊！ ### **4.【实现细节】** - 子连通块大小不要直接用 $\text{size(to)}$（这都是从淀粉质那里遗留下来的问题了，但依旧有人不重视） - 一般不需要把虚树的实际形态建出来，但如果能用到的话，注意不要和原树搞混。 - 树状数组大小要设置得当。设 $now=|subtree(i)|$，由于 $i$ 在 $subtree(i)$ 中为重心，所以 $f_1(i,j)$ 中 $j$ 的值域为 $[0\sim \frac{now}{2}]$，$f_2(i,j)$ 中 $j$ 的值域为 $[1\sim now]$ 。由于下标可以为 $0$，在树状数组内部还需要统一向后移一位。也就是说 $f_1,f_2$ 的大小要分别设置为 $\frac{now}{2}+1$ 和 $now+1$ 。 - 如果预处理了每个点在虚树上的祖先，修改 / 查询中跳父亲时需要倒序枚举（具体见代码）。 - 关于卡常：点分树做题经常会用到 $\text{vector},$ $\text{set},$ $\text{multiset},$ $\text{priority queue}$ 之类的东西，如果您嫌弃它们太慢且不愿开 $\text{O2}$，自备几个能代替 $\text{STL}$ 的模板吧.... ### **5.【Code】** （线段树的代码就不放了） **【在线查询 Dis】** ```cpp #include<algorithm> #include<cstring> #include<cstdio> #include<vector> #define LL long long #define Re register int using namespace std; const int N=1e5+3,inf=2e9,logN=17; int n,m,o,x,y,T,op,lastans,A[N],deep[N],head[N]; struct QAQ{int to,next;}a[N<<1]; inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;} inline void in(Re &x){ int f=0;x=0;char c=getchar(); while(c<'0'||c>'9')f|=c=='-',c=getchar(); while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar(); x=f?-x:x; } struct LCA{ int fa[N],top[N],son[N],size[N]; inline void dfs1(Re x,Re Fa){ size[x]=1,deep[x]=deep[fa[x]=Fa]+1; for(Re i=head[x],to;i;i=a[i].next) if((to=a[i].to)!=Fa){ dfs1(to,x),size[x]+=size[to]; if(size[son[x]]<size[to])son[x]=to; } } inline void dfs2(Re x,Re rt){ top[x]=rt; if(!son[x])return; dfs2(son[x],rt); for(Re i=head[x],to;i;i=a[i].next) if((to=a[i].to)!=fa[x]&&to!=son[x])dfs2(to,to); } inline void build(){dfs1(1,0),dfs2(1,1);} inline int lca(Re x,Re y){ while(top[x]!=top[y]){ if(deep[top[x]]<deep[top[y]])swap(x,y); x=fa[top[x]]; } if(deep[x]>deep[y])swap(x,y); return x; } }T1; inline int Dis(Re x,Re y){return deep[x]+deep[y]-(deep[T1.lca(x,y)]<<1);}//查询原树中点x,y的距离 struct BIT{ int n;vector<int>C; inline void build(Re N){C.resize((n=N)+1);}//使用到的上限为n,空间开n+1 inline void add(Re x,Re v){++x;while(x<=n)C[x]+=v,x+=x&-x;}//由于dis可能为0,所以在BIT里面统计向后移一位，查询同理 inline int ask(Re x){++x,x=min(x,n);Re ans=0;while(x)ans+=C[x],x-=x&-x;return ans;}//注意要和维护的上界取最小值，防止越界 }TR1[N],TR2[N]; int rt,sum,fa[N],vis[N],maxp[N],size[N]; inline void getrt(Re x,Re fa){//获取该连通块的重心 size[x]=1,maxp[x]=0; for(Re i=head[x],to;i;i=a[i].next) if(!vis[to=a[i].to]&&to!=fa) getrt(to,x),size[x]+=size[to],maxp[x]=max(maxp[x],size[to]); maxp[x]=max(maxp[x],sum-size[x]); if(maxp[x]<maxp[rt])rt=x; } inline void sakura(Re x,Re Fa){//处理重心x所囊括的连通块 Re now=sum;vis[x]=1,fa[x]=Fa; TR1[x].build(now/2+1),TR2[x].build(now+1);//由重心性质可知,TR1会使用[0,now/2],TR2会使用[1,now]，向后移一位变为[1,now/2+1]和[2,now+1] for(Re i=head[x],to;i;i=a[i].next) if(!vis[to=a[i].to]) sum=size[to]>size[x]?now-size[x]:size[to],maxp[rt=0]=inf,getrt(to,0),sakura(rt,x);//注意子连通块大小不要直接用size[to] } inline void change(Re x,Re v){ TR1[x].add(0,v);//subtree(x) for(Re i=x;fa[i];i=fa[i]){//在虚树上面跳父亲 Re tmp=Dis(x,fa[i]); TR1[fa[i]].add(tmp,v); TR2[i].add(tmp,v); } } inline int ask(Re x,Re K){ Re ans=TR1[x].ask(K);//subtree(x) for(Re i=x;fa[i];i=fa[i]){//在虚树上面跳父亲 Re tmp=Dis(x,fa[i]);if(tmp>K)continue; ans+=TR1[fa[i]].ask(K-tmp); ans-=TR2[i].ask(K-tmp); } return ans; } int main(){ // freopen("123.txt","r",stdin); in(n),in(T),m=n-1; for(Re i=1;i<=n;++i)in(A[i]); while(m--)in(x),in(y),add(x,y),add(y,x); T1.build(),sum=n,maxp[rt=0]=inf,getrt(1,0),sakura(rt,0); for(Re i=1;i<=n;++i)change(i,A[i]); while(T--){ in(op),in(x),in(y),x^=lastans,y^=lastans; if(op)change(x,y-A[x]),A[x]=y; else printf("%d\n",lastans=ask(x,y)); } } ``` **【预处理 Dis】** ```cpp #include<algorithm> #include<cstring> #include<cstdio> #include<vector> #define LL long long #define Re register int using namespace std; const int N=1e5+3,inf=2e9,logN=17; int n,m,o,x,y,T,op,lastans,A[N],head[N]; struct QAQ{int to,next;}a[N<<1]; inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;} inline void in(Re &x){ int f=0;x=0;char c=getchar(); while(c<'0'||c>'9')f|=c=='-',c=getchar(); while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar(); x=f?-x:x; } struct BIT{ int n;vector<int>C; inline void build(Re N){C.resize((n=N)+1);}//使用到的上限为n,空间开n+1 inline void add(Re x,Re v){++x;while(x<=n)C[x]+=v,x+=x&-x;}//由于dis可能为0,所以在BIT里面统计向后移一位，查询同理 inline int ask(Re x){++x,x=min(x,n);Re ans=0;while(x)ans+=C[x],x-=x&-x;return ans;}//注意要和维护的上界取最小值，防止越界 }TR1[N],TR2[N]; int rt,sum,gs[N],vis[N],maxp[N],size[N],frt[N][20],fdis[N][20]; inline void getrt(Re x,Re fa){//获取该连通块的重心 size[x]=1,maxp[x]=0; for(Re i=head[x],to;i;i=a[i].next) if(!vis[to=a[i].to]&&to!=fa) getrt(to,x),size[x]+=size[to],maxp[x]=max(maxp[x],size[to]); maxp[x]=max(maxp[x],sum-size[x]); if(maxp[x]<maxp[rt])rt=x; } inline void getdis(Re x,Re rt,Re fa,Re d){//遍历该连通块预处理dis frt[x][++gs[x]]=rt,fdis[x][gs[x]]=d;//顺手把祖先也存下来，后面一起访问 for(Re i=head[x],to;i;i=a[i].next) if(!vis[to=a[i].to]&&to!=fa)getdis(to,rt,x,d+1); } inline void sakura(Re x){//处理重心x所囊括的连通块 Re now=sum;vis[x]=1,getdis(x,x,0,0); TR1[x].build(now/2+1),TR2[x].build(now+1);//由重心性质可知,TR1会使用[0,now/2],TR2会使用[1,now]，向后移一位变为[1,now/2+1]和[2,now+1] for(Re i=head[x],to;i;i=a[i].next) if(!vis[to=a[i].to]) sum=size[to]>size[x]?now-size[x]:size[to],maxp[rt=0]=inf,getrt(to,0),sakura(rt);//注意子连通块大小不要直接用size[to] } inline void change(Re x,Re v){ TR1[x].add(0,v);//subtree(x) for(Re i=gs[x];i>=2;--i){//注意要倒序枚举 Re tmp=fdis[x][i-1]; TR1[frt[x][i-1]].add(tmp,v); TR2[frt[x][i]].add(tmp,v); } } inline int ask(Re x,Re K){ Re ans=TR1[x].ask(K);//subtree(x) for(Re i=gs[x];i>=2;--i){//注意要倒序枚举 Re tmp=fdis[x][i-1];if(tmp>K)continue; ans+=TR1[frt[x][i-1]].ask(K-tmp); ans-=TR2[frt[x][i]].ask(K-tmp); } return ans; } int main(){ // freopen("123.txt","r",stdin); in(n),in(T),m=n-1; for(Re i=1;i<=n;++i)in(A[i]); while(m--)in(x),in(y),add(x,y),add(y,x); sum=n,maxp[rt=0]=inf,getrt(1,0),sakura(rt); for(Re i=1;i<=n;++i)change(i,A[i]); while(T--){ in(op),in(x),in(y),x^=lastans,y^=lastans; if(op)change(x,y-A[x]),A[x]=y; else printf("%d\n",lastans=ask(x,y)); } } ``` ## **三：【常见套路、经典例题】** （**注：** 后面的题都不再用文字具体阐述 $f_1,f_2$ 含义，且只放核心代码） ### **1.【另外两道板题】** - [**烁烁的游戏** $\text{[Bzoj4372]}$](http://lydsy.com/JudgeOnline/problem.php?id=4372) （和模板题震波类似，用一个数据结构进行维护） - [$\text{Atm}$ **的树** $\text{[Bzoj4317] [Bzoj2051] [Bzoj2117]}$](http://www.lydsy.com/JudgeOnline/problem.php?id=4317)（二分答案后又是一只震波） ### **2.【开店】** **[开店 $\text{[HNOI2015] [P3241]}$](https://www.luogu.com.cn/problem/P3241)** **【题目大意】** 维护一颗带点权、边权树，每次给出 $x,l,r$，查询 $\sum_{l\leqslant A_y \leqslant r}dis(x,y)$，其中 $A_y$ 为 $y$ 的点权。说起这道题，想起一张图（来自 $\text{hychyc}$ 巨佬的[主席树做法](https://www.luogu.com.cn/blog/hychyc/hnoi2015-kai-dian)） ![](https://cdn.luogu.com.cn/upload/image_hosting/fdnivxcr.png) （窝还是老老实实打点分树吧...） ![](https://cdn.luogu.com.cn/upload/image_hosting/8y6q8i0f.png) #### **(1).【分析】** 统计贡献还是和模板题一样的套路，设： $f_1(i,j)=\sum_{x\in subtree(i),A_x\leqslant j}dis(x,i)

f_2(i,j)=\sum_{x\in subtree(i),A_x\leqslant j}dis(x,fa_i)

在查询点 x 的答案时，上面只算了合法点到祖先的距离，漏掉了 x 到 fa_i 这一段，所以还要记点数：

查询时差分一下，只算权值小于等于 $k$ 的距离之和。则有 $ans(x,k)=f_1(x,k)+$ $\sum_{i\in fatree(x),fa_i\neq 0} G(i,fa_i)

其中 G(i,fa_i)= f_1(fa_i,k)-f_2(i,k) +dis(x,fa_i)\times (g_1(fa_i,k)-g_1(i,k)) 。

由于这题没有修改操作，所以直接在建虚树时开个 \text{vector} 预排序，顺便求出前缀和，查询时二分位置即可。

另外，为减小常数可以把柿子拆开，在一次 k 查询中对于虚树上每个祖先只使用一次二分。

空间复杂度：O(n\log n) 。

时间复杂度：O((n+q)\log^2 n) 。

(2).【Code】

struct QWQ{
    int v;LL S1,S2;QWQ(Re V=0,LL s1=0,LL s2=0){v=V,S1=s1,S2=s2;}
    inline bool operator<(const QWQ &O)const{return v<O.v;}
};
vector<QWQ>TR[N];
inline void getdis(Re x,Re fa,Re rt,Re d){
    TR[rt].push_back(QWQ(A[x],d,Fa[rt]?Dis(x,Fa[rt]):0));//如果rt没有父亲就不要求dis了
    for(Re i=head[x],to;i;i=a[i].next)if(!vis[to=a[i].to]&&to!=fa)getdis(to,x,rt,d+a[i].w);
}
inline void sakura(Re x){
    Re now=sum;vis[x]=1,getdis(x,0,x,0);
    sort(TR[x].begin(),TR[x].end());//预排序
    for(Re i=1;i<now;++i)TR[x][i].S1+=TR[x][i-1].S1,TR[x][i].S2+=TR[x][i-1].S2;//前缀和
    for(Re i=head[x],to;i;i=a[i].next)if(!vis[to=a[i].to])
        sum=size[to]>size[x]?now-size[x]:size[to],maxp[rt=0]=inf,getrt(to,0),Fa[rt]=x,sakura(rt);
}
inline QWQ get(Re x,Re K){//获取权值小于等于K的点信息之和
    vector<QWQ>::iterator it=upper_bound(TR[x].begin(),TR[x].end(),QWQ(K));
    if(it==TR[x].begin())return QWQ();--it;return QWQ((it-TR[x].begin())+1,it->S1,it->S2);
}
inline LL ask(Re x,Re K){//查询权值小于等于K的点与x的距离之和
    QWQ TR=get(x,K);LL ans=TR.S1;
    if(Fa[x])ans-=TR.S2+(LL)Dis(x,Fa[x])*TR.v;//为迎合拆柿子,这里把第一次计算拿出来了
    for(Re i=Fa[x];i;i=Fa[i]){
        TR=get(i,K),ans+=TR.S1+(LL)Dis(x,i)*TR.v;
        if(Fa[i])ans-=TR.S2+(LL)Dis(x,Fa[i])*TR.v;
    }
    return ans;
}

3.【幻想乡战略游戏】

幻想乡战略游戏 \text{[ZJOI2015] [P3345]}

【题目大意】 维护一颗带点权、边权树（树上点的度数不超过 20）。现有若干次修改点权的操作，每次操作结束后您需要选出一个核心点 x 使得 F(x) 最小，其中 F(x)=\sum_{i=1}^{n}dis(x,i)\times A_i，A_i 为 i 的点权。

(1).【分析】

这题关键在于分析性质~~猜结论~~。

假设当前核心为 x，将 x 设为树的根，定义 S_A(i) 为 i 子树内所有点的点权之和。

对于 x 的任意一个儿子节点 y，若将核心改为 y，那么 \Delta F_{x \to y} =F(y)-F(x)=(S_A(x)-2S_A(y))\times dis(x,y) 。选 y 更优当且仅当满足 \Delta F_{x \to y}<0 即 S_A(x)<2S_A(y)，易知对于一个 x 满足该式的 y 最多只存在一个。

于是一个经过优化的暴力就产生了：每次询问从根开始，不断进入比它更优的儿子，如果找不到更优则说明本身已是最优。

但很多人只讲到这些就开始扯点分树信息维护了，实际上是不严谨的，我们还需要证明：“在以 x 为根时，若 y 没有 x 优秀（表现为 \Delta F_{x \to y}>0），则 y 子树里的点也一定没有 x 优秀”。

设 y 的儿子为 y'，考虑还是在以 x 为根的前提下记算贡献：
\Delta F_{y \to y'}$ $=(S_A(y)-2S_A(y')+S_A(x)-S_A(y))\times dis(y,y')$ $=(S_A(x)-2S_A(y'))\times dis(y,y')
又因为 S_A(y)\geqslant S_A(y')（这题 A_i 应该是不为负的，所以能得出这个关系式）
若 \Delta F_{x \to y}>0 则 S_A(x)>2S_A(y)\geqslant 2S_A(y')
因此 \Delta F_{y \to y'}>0, \Delta F_{x \to y'}=\Delta F_{x \to y}+\Delta F_{y \to y'}>0 。
证毕。

暴力单次询问复杂度 O(20depth)，而点分树有着 depth=O(\log n) 的天然优势，我们可以把跳儿子的过程转移到点分树上进行。具体的说，从第一个重心开始，枚举它在原树上的儿子，若找到了比他更优的点，则跳到该子树（或者说子连通块）的重心。容易证明这样做一定不会错过最优解。

现在的问题只剩下快速计算 F(x) 了，按照套路，设：

f_1(i)=\sum_{x\in subtree(i)}dis(x,i)\times A_x

f_2(i)=\sum_{x\in subtree(i)}dis(x,fa_i)\times A_x

g_1(i)=\sum_{x\in subtree(i)}A_x

则有 F(x)=f_1(x)+ \sum_{i\in fatree(x),fa_i\neq 0} G(i,fa_i)

其中 G(i,fa_i)= f_1(fa_i)-f_2(i) +dis(x,fa_i)\times (g_1(fa_i)-g_1(i)) 。

由于这题的 f_1,f_2,g_1 都只有一维，直接用数组存下来就好了。

空间复杂度：O(n\log n) 。

时间复杂度：O(n\log n+20q\log^2n) 。

（这题不知为啥常数小得惊人，不吸氧最慢的点只跑了 900ms）

(2).【Code】

inline void change(Re x,Re v){//Sv即为g1
    TR1[x]+=v*0,Sv[x]+=v;
    for(Re i=gs[x];i>=2;--i){
        Re tmp=fdis[x][i-1];
        TR1[frt[x][i-1]]+=(LL)v*tmp;
        TR2[frt[x][i]]+=(LL)v*tmp;
        Sv[frt[x][i-1]]+=v;
    }
}
inline LL ask(Re x){//计算F(x)
    LL ans=TR1[x];
    for(Re i=gs[x];i>=2;--i){
        Re tmp=fdis[x][i-1];
        ans+=TR1[frt[x][i-1]];
        ans-=TR2[frt[x][i]];
        ans+=(LL)(Sv[frt[x][i-1]]-Sv[frt[x][i]])*tmp;
    }
    return ans;
}
inline LL find(Re x){
    LL tmp=ask(x);
    for(Re i=T0.head[x];i;i=T0.a[i].next)//这里枚举原树
        if(ask(T0.a[i].to)<tmp)return find(T0.a[i].rt);//如果to比x优秀就进入to所在连通块的重心（x在虚树上的儿子）
    return tmp;
}

4.【小清新数据结构题】

小清新数据结构题 \text{[P3676]}

【题目大意】 维护一颗带点权树，需要支持两种操作：修改 x 的点权，查询以点 x 为根时的 \sum_{i=1}^{n}(\sum_{j\in sub(i)}A_j)^2，其中A_j 为 j 的点权，sub(i) 为点 i 子树内的节点集合。

(1).【分析】

一看就知道是个~~丧心病狂~~拆柿子题。

上公式（以 x 为根）：

设 sum=\sum_{i=1}^{n}A_i，S(i)=\sum_{j\in sub(i)}A_j

设 $F=\sum_{i=1}^{n}dis(i,x)\times A_i$（用与 [幻想乡战略游戏](https://www.luogu.com.cn/problem/P3345) 同样的方法可以求得）由于 $\sum_{i=1}^{n}S_i(sum-S_i)$ 始终为一个定值（对于每条边 $x,y$，两边的连通块点权之和乘起来然后再求和），我们可以先 $O(n)$ 预处理出来，设为 $tmp$ 。则 $ans(x)=\sum_{i=1}^{n}S_i^2$ $=sum\sum_{i=1}^{n}S_i-tmp$ $=sum(sum+F)-tmp$ 。空间复杂度：$O(n\log n)$ 。时间复杂度：$O((n+q)\log n)$ 。 #### **(2).【Code】** 代码就不放了，毕竟和上一道差不多，只是多了个 $dfs$ 预处理 $tmp$。 ![](https://cdn.luogu.com.cn/upload/image_hosting/gq7ndcc6.png) ### **5.【成都七中】** **[成都七中 $\text{[Ynoi2011] [P5311]}$](https://www.luogu.com.cn/problem/P5311)** **【题目大意】** 由一颗树，树上每个节点有一种颜色，每次查询给出 $l,r,x$，求保留树上编号在 $[l,r]$ 内的点，$x$ 所在联通块中颜色种类数。 #### **(1).【分析】** 这题比较难想。先建出点分树，对于一次查询 $(l,r,x)$，在点分树上 $x$ 的祖先中找到深度最小的点 $pa$，且满足 $x$ 只经过编号 $[l,r]$ 内的点在原树上能到达 $pa$ 。记一下每个点 $i$ 到虚树祖先的路径上所经过的节点编号最小/大值就可以轻松求得（分别记为 $d_{min}(i,j)$ 和 $d_{max}(i,j)$）。分析可知：$x$ 只经过编号 $[l,r]$ 内的点所在的连通块被完全包含在了 $subtree(pa)$ 中（虚子树）。我们把本次询问放到 $pa$ 节点处，最后再统一离线处理。枚举虚树上的点 $rt$，处理该节点处的询问时，对于任意一个 $(l,r,x)$，满足 $l\leqslant d_{min}(i,rt)$ 且 $d_{max}(i,rt)\leqslant r$ 的 $i$ 即为与 $x$ 在同一连通块内的点，现需要统计这些点的颜色种类。显然是个偏序问题，把询问和节点信息放一起按 $l$ 排序，指针从右往左扫，同时记录每种颜色节点右端点最小的位置，再开一棵树状数组维护每个位置上的数量，便可直接查询了。空间复杂度：$O(n\log n)$ 。时间复杂度：$O(n\log^2 n)$ 。 #### **(2).【Code】** ```cpp struct Query{int l,r,id,co;inline bool operator<(const Query &O)const{return l!=O.l?l>O.l:id<O.id;}};vector<Query>Q[N]; inline void getdis(Re x,Re rt,Re fa,Re d1,Re d2){//d1:最小值 d2:最大值 d1=min(d1,x),d2=max(d2,x),Q[rt].push_back((Query){d1,d2,0,A[x]}); frt[x][++gs[x]]=rt,fd1[x][gs[x]]=d1,fd2[x][gs[x]]=d2; for(Re i=head[x],to;i;i=a[i].next)if(!vis[to=a[i].to]&&to!=fa)getdis(to,rt,x,d1,d2); } inline void change(Re x,Re l,Re r,Re id){//插入第id次询问l,r,x for(Re i=1;i<=gs[x];++i) if(l<=fd1[x][i]&&fd2[x][i]<=r){Q[frt[x][i]].push_back((Query){l,r,id,0});break;} } struct BIT{ int C[N]; inline void CL(Re x){while(x<=n)C[x]=0,x+=x&-x;} inline void add(Re x,Re v){while(x<=n)C[x]+=v,x+=x&-x;} inline int ask(Re x){Re ans=0;while(x)ans+=C[x],x-=x&-x;return ans;} }TR; inline int GetAns(){ for(Re i=1;i<=100000;++i)mir[i]=inf; for(Re rt=1;rt<=n;++rt){//枚举点分树上的点 sort(Q[rt].begin(),Q[rt].end()); for(IT it=Q[rt].begin();it!=Q[rt].end();++it) if(it->id)Ans[it->id]=TR.ask(it->r);//查询 else if(it->r<mir[it->co])TR.add(mir[it->co],-1),TR.add(mir[it->co]=it->r,1);//节点信息，更新此颜色的最小右端点 for(IT it=Q[rt].begin();it!=Q[rt].end();++it) if(!(it->id))TR.CL(mir[it->co]),mir[it->co]=inf; } } ``` ### **6.【Iqea】** [$\text{Iqea}$](https://www.luogu.com.cn/problem/CF936E) [$\text{[CF936E]}$](http://codeforces.com/problemset/problem/936/E) **【题目大意】** 二维平面上给出若干个点的坐标，在这些点处打好地基（保证为一个四连通块，且不会出现封闭的空地）。有两种操作：在 $(x,y)$ 处建造商店，询问离 $(x,y)$ 最近的商店与 $(x,y)$ 的距离大小。两点距离定义为只经过有地基的点的最短路径长度，相邻两个格子距离为 $1$ 。保证每次给出的坐标处一定有地基。 #### **(1).【分析】** 一只神薙。首先是非常巧妙的建图：每一行分开看，把同一行的若干个联通块分别缩成点，然后向四周相邻的点连边，由于没有封闭的空地，这样连出来一定是棵树。支持加入关键点，查询距离最近的关键点，建点分树？似乎还没做完：两点之间的最短距离要如何在树上表示呢？看图： ![](https://cdn.luogu.com.cn/upload/image_hosting/3yqbzuu9.png) 任选 $a,b$ 路径上一个缩成点的小连通块 $m$ 作为中介（如图中黄色框），先分别求出 $a,b$ 移动到中介的最短路径 $d_a(m),d_b(m)$，并记录它们到达中介时的纵坐标 $y_a(m),y_b(m)$（在图中表现为 $1$ 号和 $8$ 号位置），则 $dis(a,b)=d_a(m)+d_b(m)+|y_a(m)-y_b(m)|$，即 $\min\{d_a(m)+d_b(m)+y_a(m)-y_b(m),d_a(m)+d_b(m)+y_b(m)-y_a(m)\}$ 。现在点分树就可以轻松维护答案了，设： $f_1(i,j)=\sum_{x\in subtree(i),y_x(i)\leqslant j}d_x(i)-y_x(i)

g_1(i,j)=\sum_{x\in subtree(i),y_x(i)\geqslant j}d_x(i)+y_x(i)

则有 ans(x,k)= \min_{i\in fatree(x)} \min\{d_x(i)+y_x(i)+f_1(i,y_x(i)),d_x(i)-y_x(i)+g_1(i,y_x(i))\}

二维的 f_1,g_1 用树状数组维护。

空间复杂度：O(n\log n) 。

时间复杂度：O(n\log n+q\log^2 n) 。

(2).【Code】

int ip_O,n,o,x,y,T,op,MaxX,X[N],ip[N],Yl[N],Yr[N],idl[N],idr[N],head[N];vector<int>V[N];map<int,int>id[N];
struct QAQ{int to,next;}a[N<<1];//外层的这个是缩图所得到的树
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
struct Tree{
    int o,head[N];
    struct QAQ{int to,next;}a[N<<2];
    inline void add_(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
    inline void add(Re x,Re y){add_(x,y),add_(y,x);}
}T0;//T0:以二维平面上的连通性建成的图
inline void get_tree(){//缩图建树
    for(Re i=1;i<=n;++i)in(x),in(y),MaxX=max(MaxX,x),V[x].push_back(y),id[x][y]=i;
    for(Re x=1;x<=MaxX;++x)if(!V[x].empty()){
        sort(V[x].begin(),V[x].end());
        Re last=-1;idl[x]=ip_O+1;
        for(Re J=0,SZ=V[x].size(),y;J<SZ;last=V[x][J],++J){
            if(last+1!=(y=V[x][J]))ip[id[x][y]]=++ip_O,X[ip_O]=x,Yl[ip_O]=Yr[ip_O]=y;
            else ip[id[x][y]]=ip_O,Yr[ip_O]=y,T0.add(id[x][y],id[x][y-1]);
            if(id[x-1].find(y)!=id[x-1].end())T0.add(id[x-1][y],id[x][y]);
        }
        idr[x]=ip_O;
        if(V[x-1].empty())continue;
        Re k=idl[x-1];
        for(Re j=idl[x];j<=idr[x];++j){
            while(k<=idr[x-1]&&Yr[k]<Yl[j])++k;
            for(Re k_=k;k_<=idr[x-1]&&Yl[k_]<=Yr[j];++k_)add(k_,j),add(j,k_);
        }
    }
}
struct QWQ{
    int d,y;QWQ(Re D=0,Re Y=0){d=D,y=Y;}
    inline bool operator<(const QWQ &O)const{return d<O.d;}
};
struct BIT{
    int n,op;vector<int>C;//op=0:前缀  op=1:后缀(把询问、查询里的x都翻转一下就是了)
    inline void build(Re N){n=N,C.push_back(inf);while(N--)C.push_back(inf);}//这里就不用resize了,因为要初始化为inf
    inline void add(Re x,Re v){if(op)x=n-x+1;while(x<=n)C[x]=min(C[x],v),x+=x&-x;}
    inline int ask(Re x){if(op)x=n-x+1;Re ans=inf;while(x)ans=min(ans,C[x]),x-=x&-x;return ans;}
}TR1[N],TR2[N];
int rt,sum,gs[N],vis[N],maxp[N],size[N],frt[N][22];QWQ fdis[N][22];
inline void getrt(Re x,Re fa){
    size[x]=Yr[x]-Yl[x]+1,maxp[x]=0;//注意size的初始化不是1
    for(Re i=head[x],to;i;i=a[i].next)if(!vis[to=a[i].to]&&to!=fa)
        getrt(to,x),size[x]+=size[to],maxp[x]=max(maxp[x],size[to]);
    maxp[x]=max(maxp[x],sum-size[x]);if(maxp[x]<maxp[rt])rt=x;
}
int Q[N],pan[N];QWQ dis[N];
inline void getdis0(Re rt){//bfs
    Re h=1,t=0;
    for(Re i=Yl[rt];i<=Yr[rt];++i)pan[Q[++t]=id[X[rt]][i]]=rt,dis[Q[t]]=QWQ(0,i-Yl[rt]+1);
    while(h<=t){
        Re x=Q[h++];
        for(Re i=T0.head[x],to;i;i=T0.a[i].next)
            if(pan[to=T0.a[i].to]!=rt&&!vis[ip[to]])
                dis[to]=QWQ(dis[x].d+1,dis[x].y),pan[Q[++t]=to]=rt;
    }
}
inline void getdis(Re x,Re rt,Re fa){
    frt[x][++gs[x]]=rt;
    for(Re i=Yl[x];i<=Yr[x];++i)fdis[id[X[x]][i]][gs[x]]=dis[id[X[x]][i]];//距离在bfs中已获得
    for(Re i=head[x],to;i;i=a[i].next)if(!vis[to=a[i].to]&&to!=fa)getdis(to,rt,x);
}
inline void sakura(Re x){
    Re now=sum;vis[x]=1,getdis0(x),getdis(x,x,0);
    TR1[x].build(Yr[x]-Yl[x]+1),TR2[x].build(Yr[x]-Yl[x]+1),TR2[x].op=1;//树状数组的使用范围为[1,Yr-Yl+1]
    for(Re i=head[x],to;i;i=a[i].next)if(!vis[to=a[i].to])
        sum=size[to]>size[x]?now-size[x]:size[to],maxp[rt=0]=inf,getrt(to,0),sakura(rt);
}
inline void change(Re y){
    Re x=ip[y];
    for(Re i=gs[x];i;--i)
        TR1[frt[x][i]].add(fdis[y][i].y,fdis[y][i].d-fdis[y][i].y),
        TR2[frt[x][i]].add(fdis[y][i].y,fdis[y][i].d+fdis[y][i].y);
}
inline int ask(Re y){
    Re x=ip[y],ans=inf;
    for(Re i=gs[x];i;--i)
        ans=min(ans,fdis[y][i].d+fdis[y][i].y+TR1[frt[x][i]].ask(fdis[y][i].y)),
        ans=min(ans,fdis[y][i].d-fdis[y][i].y+TR2[frt[x][i]].ask(fdis[y][i].y));
    return ans;
}

7.【大毒瘤】

~~相信您已经积累了足够的实力，下面我们来看一道果题吧QAQ~~

紫荆花之恋 \text{[WC2014] [P3920]}

四：【总结】

模板及例题 1.1,1.2 都是靠数据结构维护贡献，例 2 则换成了 \text{STL} 。套娃行为所导致的的码量增加以及大常数都是值得关注的问题。

例 3,4 主要是按照容斥套路推式子，相对比较好掌握，但细节较多，要注意统计贡献时补充不漏。

例 5 难点在于利用点分树的特殊性质转离线。点分树各种神奇的特性，对应到不同的题上就会有各种神奇的解法。如果没有强大的瞎蒙猜结论能力，就多刷刷题吧，见多识广总没有坏处的。

例 6 不光要会神仙建图，还要想办法用点分树能维护的东西来表示两点距离。这道题有效地提醒了我们：点分树有着不错的灵活性，并非只有那个一成不变的模板，所以不要死记硬背啊...

Q: 话说点分树能搞可持久化吗？
A: 虽然听起来比较毒瘤，但不瞒您说，还真可以（具体见可持久化点分树）

五：【参考资料】

震波题解 \text{by Enigma-aw}
开店题解 \text{by shadowice1984}
\text{Iqea} 题解 \text{by Dream-Lolita}
可持久化点分树 \text{by JhinLZH}