擅长捉弄夫人的高木同学


前言

本来在学概率期望的,然而学长要讲点分治,好像还不讲板子于是过来学了。

点分治一般用于解决树上路径统计问题(满足某某条件的路径有多少条)。

顺便把点分树学了。


抄袭来源

「算法竞赛·进阶指南」?

https://oi-wiki.org/graph/dynamic-tree-divide/


#define

$siz(i)$:子树$i$的大小。

$ma(i)$:将点$i$从树中去掉后,产生的新子树中最大的$siz$。

树的重心:$ma$最小的点。

$dis(i)$:点$i$到根的距离。

$deep(i)$:点$i$到根的边数。

$tax$:桶。

$root$:当前分治中心。


树的重心

去掉一个点,产生的新子树就是它儿子和爹的子树,一个$O(n)$的做法就很显然了:

int siz[maxn],all,mx=inf,root;//all为原树大小,mx为当前ma最小的点,root为重心
void get_point(int node,int f){
    siz[node]=1;
    int x,ma=0;
    for(register int i=h[node];i;i=e[i].pre){
        x=e[i].to;
        if(x!=f)get_point(x,node),siz[node]+=siz[x],ma=max(ma,siz[x]);
    }
    ma=max(ma,all-siz[node]);
    if(ma<mx)mx=ma,root=node;
}

点分治

实现

对于一棵树,路径无非有两种:经过根的路径和根子树内部的路径。

我们先统计出经过根的路径,再把根的每个子树递归下去。

当然会被链卡成$O(n^2)$的,选取树的重心递归就能稳定$O(n\log n)$。

栗子

在根的两个不同子树中取两个点$x,y$,满足$dis(x)+dis(y)=k$就满足条件。

$k$只有$1e7$,开个$1e7$的桶暴力统计即可。

代码

由于是自己yy的所以十分丑陋

int tax[10000001]={1},siz[maxn],h[maxn],all,ma,root,num,k;
bool vis[maxn],ans;
struct edge{
    int pre,to,l;
}e[maxn<<1];
inline void add(int from,int to,int l){
    e[++num].pre=h[from],h[from]=num,e[num].to=to,e[num].l=l;
}
void get_point(int node,int f=0){
    siz[node]=1;
    int mx=0,x;
    for(register int i=h[node];i;i=e[i].pre){
        x=e[i].to;
        if(x!=f&&!vis[x])get_point(x,node),siz[node]+=siz[x],mx=max(siz[x],mx);
    }
    mx=max(mx,all-siz[node]);
    if(mx<ma)ma=mx,root=node;
}
void Count(int node,int len,int v,int f=0){
    if(len>k)return;
    int x;
    for(register int i=h[node];i;i=e[i].pre){
        x=e[i].to;
        if(x!=f&&!vis[x])Count(x,len+e[i].l,v,node);
    }
    tax[len]+=v;
}//计算答案
void calc(int node,int len,int f=0){
    if(len>k)return;
    int x;
    for(register int i=h[node];i;i=e[i].pre){
        x=e[i].to;
        if(x!=f&&!vis[x])calc(x,len+e[i].l,node);
    }
    ans|=tax[k-len];
}//统计
void calc_siz(int node,int f=0){
    siz[node]=1;
    int x;
    for(register int i=h[node];i;i=e[i].pre){
        x=e[i].to;
        if(x==f||vis[x])continue;
        calc_siz(x,node),siz[node]+=siz[x];
    }
}
void solve(int node){
    int x;
    vis[node]=1;
    for(register int i=h[node];i;i=e[i].pre){
        x=e[i].to;
        if(!vis[x])calc(x,e[i].l),Count(x,e[i].l,1);//先算答案再统计,否则子树内部会影响
    }
    for(register int i=h[node];i;i=e[i].pre){
        x=e[i].to;
        if(!vis[x])Count(x,e[i].l,-1);
    }//清空桶子
    calc_siz(node);
    for(register int i=h[node];i;i=e[i].pre){
        x=e[i].to;
        if(!vis[x])all=siz[x],ma=inf,get_point(x),solve(root);
    }//递归计算子树 
}
int main(){
    int n=read(),m=read(),x,y,z;
    for(register int i=1;i<n;++i)x=read(),y=read(),z=read(),add(x,y,z),add(y,x,z);
    while(m--)memset(vis,0,sizeof vis),k=read(),all=n,ma=inf,ans=0,get_point(1),solve(root),puts(ans?"AYE":"NAY");
}

点分树

栗子

单独拿出一个询问,不求树的直径,可以用点分治解决。

现在带修了,于是点分树来了。

实现

先考虑朴素的点分治。

为了方便点分树的食用,统计时用一种繁琐的方法:

对$root$的每个儿子,$dfs$算出子树内最大$deep$,选取最大的两个加和就是$root$的答案。

答案就是每个$root$的最大值。

注意到,修改一个点只会影响到它上面的$root$的答案,而每个点所属的$root$是$\log n$级别的!

把$root$向下一层的$root$连边,就能得到一棵最大深度为$\log n$的树,这就是点分树了。

一个点能影响的为其祖宗,修改直接暴力往上跳修改。

前面统计的都是最大值,为了能带修换成可删堆。

每个点记录在每个所属$root$的$deep$,在对应的堆插入/删除即可。

时间复杂度$O((m+n)\log^2 n)$,空间复杂度$O((m+n)\log n)$。

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <queue>

#define maxn 100005
#define inf 0x3f3f3f3f

using namespace std;

inline int read(){
    int x=0,y=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return y?-x:x;
}
int d[maxn][21],t[maxn][21],siz[maxn],h[maxn],fa[maxn],dc[maxn],num,root,mx=inf,all,tp;
bool vis[maxn],is[maxn];
struct edge{
    int pre,to;
}e[maxn<<1];
struct Heap{
    priority_queue<int>q,d;
    void push(int x){q.push(x);}
    void del(int x){d.push(x);}
    int top(){
        while(!d.empty()&&q.top()==d.top())q.pop(),d.pop();
        if(q.empty())return -inf;
        return q.top();
    }
    int top2(){
        int rec=top(),ans=0;
        while(!d.empty()&&q.top()==d.top())q.pop(),d.pop();
        if(!q.empty())q.pop(),ans=top();
        q.push(rec);
        return ans+rec;
    }
}son[maxn<<1],rt[maxn],ans;
inline void add(int from,int to){
    e[++num].pre=h[from],h[from]=num,e[num].to=to;
}
void getroot(int node,int f=0){
    siz[node]=1;
    int x,ma=0;
    for(register int i=h[node];i;i=e[i].pre){
        x=e[i].to;
        if(x==f||vis[x])continue;
        getroot(x,node),siz[node]+=siz[x],ma=max(ma,siz[x]);
    }
    ma=max(ma,all-siz[node]);
    if(ma<mx)mx=ma,root=node;
}
void init(int node,int f){
    son[tp].push(d[node][++dc[node]]=d[f][dc[f]]+1),t[node][dc[node]]=tp;
    int x;
    for(register int i=h[node];i;i=e[i].pre){
        x=e[i].to;
        if(x==f||vis[x])continue;
        init(x,node);
    }
}
void calc_siz(int node,int f=0){
    siz[node]=1;
    int x;
    for(register int i=h[node];i;i=e[i].pre){
        x=e[i].to;
        if(x==f||vis[x])continue;
        calc_siz(x,node),siz[node]+=siz[x];
    }
}
void build(int node){
    rt[node].push(0),vis[node]=1;
    int x;
    for(register int i=h[node];i;i=e[i].pre){
        x=e[i].to;
        if(vis[x])continue;
        ++tp,init(x,0),rt[node].push(son[tp].top());
    }
    ans.push(rt[node].top2());
    calc_siz(node);
    for(register int i=h[node];i;i=e[i].pre){
        x=e[i].to;
        if(vis[x])continue;
        all=siz[x],mx=inf,getroot(x),fa[root]=node,build(root);
    }
}
int main(){
    int n=read(),x,y,oop=n;
    char s[3];
    for(register int i=1;i<n;++i)x=read(),y=read(),add(x,y),add(y,x);
    all=n,getroot(1),build(root);
    int m=read();
    while(m--){
        scanf("%s",s);
        if(s[0]=='C'){
            x=read(),is[x]^=1;
            if(is[x]){
                --oop;
                ans.del(rt[x].top2()),rt[x].del(0),ans.push(rt[x].top2());
                for(register int i=dc[x],node=fa[x];node;--i,node=fa[node]){
                    ans.del(rt[node].top2());
                    rt[node].del(son[t[x][i]].top()),son[t[x][i]].del(d[x][i]),rt[node].push(son[t[x][i]].top());
                    ans.push(rt[node].top2());
                }
            }
            else {
                ++oop;
                ans.del(rt[x].top2()),rt[x].push(0),ans.push(rt[x].top2());
                for(register int i=dc[x],node=fa[x];node;--i,node=fa[node]){
                    ans.del(rt[node].top2());
                    rt[node].del(son[t[x][i]].top()),son[t[x][i]].push(d[x][i]),rt[node].push(son[t[x][i]].top());
                    ans.push(rt[node].top2());
                }
            }
        }
        else {
            if(!oop)puts("-1");
            else if(oop==1)puts("0");
            else printf("%d\n",ans.top());
        }
    }
}

水题

不知道受啥误导了看到单点加单点查就想用平衡树

聪聪可可

询问有多少条路径长度为$3$的倍数。

就是统计路径长度$\%3$等于$0$的路径条数,跟模板差不多。

Tree

询问有多少条路径长度$\le k$。

$calc$里查询$\le k-dis(i)$的点的数量,可以用树状数组维护,复杂度$O(n\log^2 n)$。

如果$k$更大的话可以用平衡树,清空也更方便。

Race

$k$只有$1e6$,开个桶记录$tax[len]$保存最小的$deep(i)$满足$dis(i)=len$,统计时答案对$deep(i)+tax[k-dis(i)]$取$\min$。

还可以有些小剪枝比如当$deep(i)\ge ans$时返回。

$zz$的我上来写了个$O(n\log^2 n)$的平衡树居然只比$O(n\log n)$正解慢$750ms$?

树的难题

题解

重建计划

二分答案,把树上所有边权减去当前答案,检验是否存在长度大于$0$且边数满足条件的路径。

记录每个$deep$最大的$dis$。按$deep$排序,满足条件的$deep$是一个单向移动的区间,用单调队列维护最大值,为了消掉排序的$log$需要$bfs$实现。

由于同一子树内部的路径会互相影响,对每个子树都要清空单调队列重新统计。按子树内部最大$deep$排序后可以保证复杂度为$siz(root)$。

树上游戏

神仙题。有点分治、扫描线、树上差分、虚树等各种解法。

点分治我们考虑每种颜色的贡献。开一个数组$fir$。

$dfs$一遍子树,统计出子树大小,如果在某条链上点$i$的颜色第一次出现,就将它颜色的$fir$加上$siz(i)$。

统计答案,若颜色$i$从某个点到根路径上未出现过,就会产生$fir(i)$的贡献;否则会产生$siz(root)-siz(x)$的贡献($x$为其所属子树)。

由于子树内部会互相影响,还需要先$dfs$一边减去当前子树的$fir$,统计完再加上。

剩下的就是全是细节的代码了。。。

快递员

题解


点分树的题:

震波

建出点分树,每个点维护一棵平衡树,维护该点为$root$时每个深度的点权和。

对于修改,暴力往上跳,在平衡树内修改权值。

对于查询,暴力往上跳,查询平衡树内小于等于$k-dis$的权值和。

然后会发现多加了和$x$在同一子树的点的权值,还要维护每个$root$的每棵子树的信息减去。

平衡树有个十分优美的处理方法:

把每个深度的点权和提出来,直接依照这个数组build一棵平衡树。

我们发现修改操作直接找到对应深度的点修改即可。也就是说压根没有插入删除。

于是没必要写什么平衡树,直接裸上$BST$就行$QwQ$。

(darkbzoj过了bzoj被卡常了真是恶)

开店

还是每个点维护一棵$BST$,维护该点为$root$时每个颜色的距离和和出现次数。

暴力查每棵平衡树里颜色在$[L,R]$的距离和加上$dis$乘上出现次数。同样要减去同一子树的信息。

每个点度数不超过$3$可以用来优化常数不过我不会

能在$loj$上$AC$,洛谷上$T$一个点。把$BST$换成$vector+$二分就卡过去了。

QTREE5

比较像栗子。

每个点用可删堆维护最小的$dis(i)$($i$为白点)。

查询时跳父亲,答案对查询点到当前点距离+最小$dis$取$\min$。

为了去重要维护$root$的每个儿子的堆,若当前所属儿子的堆顶等于最小$dis$则取次小$dis$。

紫荆花之恋

替罪羊式重构点分树。

题解

幻想乡战略游戏

To do