回顾树链剖分

树链剖分时,每个内部结点都会选择一个儿子做为自己链上的儿子,我们称为继承儿子(重儿子)。如果一个结点没有被继承,那么它就是一个链顶结点。一棵树剖分过后链的个数是的,其中表示叶子结点的个数。

按照树剖后的顺序先遍历继承儿子,然后遍历其他儿子,那么每条链上的结点的 DFN 序是连续的。这样可以用一个指针数组来模拟二维数组,于是就可以方便地进行一些 DP 转移。

高度

长链剖分的划分依据。设表示高度,则

形式化地,长链剖分中每个内部结点选择的是其儿子中高度最大的点作为继承结点,设其为

关于高度的性质:所在的链长度至少

长链剖分,是将高度最高的儿子结点作为继承儿子的一种剖分。在 dfs 的过程中对于每个结点,如果我们只遍历子树中除了子树之外的其他子树,那么复杂度是的。设表示子树的大小设表示所在链的链顶结点,表示的父亲,形式化地:

略证:考虑每个结点被遍历的次数。显然只会在 DFS的时候被遍历一次。因此复杂度

注意区分深度

k 级祖先

给一棵度有根树,次询问点级祖先。

这题可以容易地来做。考虑长链剖分。

首先我们倍增求出表示级祖先。另外,对于每个链顶结点,我们预处理出的前级祖先和这条链上的结点序列。

则我们先求出一个最大的使得。设,那么我们要求的就是级祖先。

由于,因此级祖先要么在所在的链上,要么在所在链的链顶结点的祖先序列上。两者都可以查询。因此分类讨论一下即可查询级祖先。

时间复杂度

代码

CF1009F

有根树。设表示一个序列,表示在子树中与距离为的点的个数。对于每个询问中最大值出现第一次的下标。

这题显然可以启发式合并。我们考虑长链剖分。

容易发现的长度为。考虑继承自。则显然有

然后我们遍历的非继承儿子,把这些儿子的序列贡献到上:

这样就求出了。然后在贡献和继承的时候顺便更新最大值即可,这样复杂度就是遍历非之外的结点的复杂度,因此总复杂度。使用 deque 实现,支持在前端插入一个数和随机访问内存,实现起来方便。(只要不遍历长链,复杂度就是对的)

模板,放出核心代码

deque<int> *d[N];
long long ans;

int dep[N],hgh[N];
int a[N],b[N];
void dfs1(int u,int p){
    dep[u]=dep[p]+1;
    hgh[u]=1;
    FORe(i,u,v)if(v!=p)dfs1(v,u),hgh[u]=max(hgh[u],hgh[v]+1);
}
void dfs2(int u,int p){
    int mx=0,son=-1;
    FORe(i,u,v)if(v!=p&&hgh[v]>mx)mx=hgh[v],son=v;
    if(son==-1){
        d[u]=new deque<int>;
        d[u]->pb(1);
        a[u]=0,b[u]=1;
        return;
    }
    dfs2(son,u);
    FORe(i,u,v)if(v!=p&&v!=son)dfs2(v,u);
    // 继承 son
    d[u]=d[son];
    d[u]->push_front(1);
    a[u]=0,b[u]=1;
    if(b[son]>b[u])b[u]=b[son],a[u]=a[son]+1;
    else if(b[son]==b[u])a[u]=min(a[u],a[son]+1);
    // 合并其他儿子的答案
    FORe(i,u,v){
        if(v==p||v==son)continue;
        int lim=(int)d[v]->size()-1;
        int mx2=0,ans=-1;
        FOR(i,0,lim){
            (*d[u])[i+1]+=(*d[v])[i];
            if((*d[u])[i+1]>mx2)mx2=(*d[u])[i+1],ans=i+1;
        }
        if(mx2>b[u])b[u]=mx2,a[u]=ans;
        else if(mx2==b[u])a[u]=min(a[u],ans);
        delete(d[v]);
    }
}

完整代码

Luogu3899

考虑长链剖分。设表示子树内与距离为的结点的子树大小减 1 的和:

则分两种情况讨论:

  1. 的祖先,则方案数为
  2. 的祖先,则方案数为

在继承的时候

在贡献的时候

考虑到我们询问的时候是一个区间和的形式,因此把做后缀和处理即可。这样可以计算询问,也可以转移,复杂度

这是指针版的写法,感觉更好用:

long long BIN[N],lb;
long long *f[N];

long long ans[N];
int hgh[N],dep[N],sz[N];
vector< pair<int,int> > qry[N];

void dfs1(int u,int p){
    hgh[u]=1,dep[u]=dep[p]+1,sz[u]=1;
    FORe(i,u,v)if(v!=p)dfs1(v,u),sz[u]+=sz[v],hgh[u]=max(hgh[u],hgh[v]+1);
}
void dfs2(int u,int p){
    ++lb;
    int mx=0,son=-1;
    FORe(i,u,v)if(v!=p&&hgh[v]>mx)mx=hgh[v],son=v;
    if(son==-1){
        f[u]=BIN+lb;// 指针赋值
        f[u][0]=sz[u]-1;
        return;
    }
    dfs2(son,u);
    FORe(i,u,v)if(v!=p&&v!=son)dfs2(v,u);

    f[u]=f[son]-1;
    f[u][0]=sz[u]-1+f[u][1];// 后缀和

    FORe(i,u,v){
        if(v==p||v==son)continue;
        FOR(i,0,hgh[v]-1)f[u][i+1]+=f[v][i];
        f[u][0]+=f[v][0];// 后缀和
    }
    // 处理询问
    for(pii p:qry[u]){
        int id=p.fi,k=p.se;
        ans[id]+=1ll*min(dep[u]-1,k)*(sz[u]-1);
        ans[id]+=f[u][1]-(k+1>=hgh[u]?0:f[u][k+1]);
    }
}

完整代码

BZOJ3252

把一个点拆成其权值长度的链。

然后在新的树上长链剖分后选前 k 大的链即可。

代码

BZOJ4543

一棵树,求三个互不相同的点并且两两距离相等的方案数。

表示子树中与距离的点的个数,表示子树中的二元组的个数,满足到其 LCA 的距离都为且这个 LCA 到的距离为。即距离差为的二元组的个数。

考虑继承

考虑贡献

这里的是指在合并完了之前的子节点的 DP 值。

考虑统计答案,我们可以在上述贡献的过程中统计:

在计算完之后,还有

注意这些转移的边界,以及他们的转移顺序。

代码

BZOJ1758

首先二分答案,则边权变成,问题转化为是否存在一条长度在的路径权值非负。

如法炮制,设表示的子树内以为端点的长度为的路径的权值最大值。

继承

贡献

这里的转移是取。在合并的时候顺便检查是否存在使得,则我们枚举的时候查询区间最大值即可。因此使用线段树维护上述转移,需要支持区间加、单点对某个数取、询问区间

时间复杂度

代码