树上邻域修改学习笔记

· · 算法·理论

本人博客，可能更好的观看体验。

前言：

树上邻域修改一直都是我没有解决的历史遗留问题，偶得闲暇，打完代码写一篇关于树上邻域修改的学习笔记。

用处：

针对树上的节点，有一些题目可能需要你对一个节点进行 d 级邻域查询或邻域修改，本篇文章提供一种每次邻域修改时间复杂度为 O(\log n \times d)，每次路径修改复杂的为 O(\log^2 n \times d)，每次子树修改时间复杂度为 O(\log n \times d) 的算法。

邻域修改：

给每个节点编号的部分在下面，作者认为先看这里更容易理解为啥那么编号，于是把这个提上来了。

如果我们只给一个节点的子树内部改 d 级的话很容易就能想到用 bfs 序，每一次扫一个节点向下的 d 层给每层修改就可以了（因为是 bfs 序，所以一行的编号是连续的，直接随便用数据结构维护一下即可）。

然后我们考虑需要增加父亲节点的情况，先不考虑超时的问题，如果增加了父亲节点的情况我们每一次给自己以及父亲节点的位置向下扫 d 层会有算重的情况（如图）：

我们考虑如何操作才能不重。

选择祖先节点 x 需要满足以下条件：

  1. x \in \mathrm{Ancestors}(v)\cup\{v\}
  2. 2\cdot\mathrm{depth}(x)\;-\;\mathrm{depth}(v)\;-\;\mathrm{depth}(u)\;\le\;k
  3. 在所有满足上述不等式的候选节点中，\mathrm{depth}(x) 最小。

其中：

这样每个节点就只会被修改一次，不会被算重了。那么考虑对于当前节点，假设领域限制为 k，那么当前节点需要修改的位置就是自己下面的第 k 行与第 k - 1 行，往自己的父亲跳时 k - 1 即可。

对于时间复杂度的分析，因为我们最多向上跳 d 层，每一次用一个数据结构维护修改的行，总时间复杂度就是 O(\log n \times d)。

节点的编号：

上面先讲的领域修改，这是我们就清晰的知道了我们梦寐以求的编号是针对一个节点向下 d 层每一层的编号都是连续的，很容易就能想到 BFS 序。如果题目中只有领域修改及查询这么写是没有问题的，但是如果题目中还有修改两个节点路径上节点的操作 BFS 序就倒闭了。而一般这种都是靠 DFS 跳重链解决，那么我们有没有一种编号方式能够兼容这两种编号方式的长处呢？

有的，兄弟有的，我们可以先对树做树链剖分，然后 dfs 一遍树，给每一个节点都向下找距离他位置在 d 之内的所有没有编号且节点在当前节点重链前 d 的节点进行 BFS 编号，这样我们就可以保证每一个节点下 d 层以内每一层被标记的点的编号是连续的。然后针对没有标记的节点做 dfs 序的普通树剖编号。

考虑这么编号对领域修改的影响，容易发现针对一个节点，如果不是和他一个重链的其他节点如果合法的话一定是 BFS 编号的节点，那么我们只用考虑自己这条链上距离他为 k 和 k - 1 的点是不是这条链前 d 的，不是就单点修改即可。

路径修改：

从上面的节点编号我们可以知道一个大概了。就像普通的树链剖分一样处理每一条链上的 DFS 序节点，然后暴力跳前 d 的点，对其单点修改即可。时间复杂度就是 O(\log^2 n \times d)。

子树修改：

如果有子树修改的操作的话，我们考虑分开考虑 DFS 序的节点与 BFS 序的节点。

针对 DFS 序节点的更改可以直接开数组记录当前子树内 DFS 序的最小值与最大值，因为是 DFS 序，所以子树内肯定是连续的，直接改即可。

针对 BFS 序节点，我们坑定也想要向 DFS 序那样简洁的修改方式。那么我们可以发现一个节点的子树内从当前根节点改的第一个节点开始的 BFS 序是连续的，那么我们只用考虑外面的节点修改当前子树的 BFS 序即可。容易发现除了根节点之外的节点都只有前 d-1 层是从外面更改过来的，直接把这些暴力跑，剩下的直接改即可。

代码：

编号：

void dfs(int p,int fa){
    tr[p].fa=fa,tr[p].siz=1;tr[p].dep=tr[fa].dep+1;
    for(int i=0;i<s[p].size();i++){
        int y=s[p][i];if(y==fa) continue;
        dfs(y,p);tr[p].siz+=tr[y].siz;
        if(tr[tr[p].son].siz<tr[y].siz) tr[p].son=y;
    }
}
void dfs1(int p,int top){v[top].push_back(p);
    tr[p].top=top;if(tr[p].son) dfs1(tr[p].son,top);
    for(int i=0;i<s[p].size();i++){
        int y=s[p][i];if(y==tr[p].fa||y==tr[p].son) continue;
        dfs1(y,y);
    }
}//正常树剖
void bfs(int ps){//修改BFS序的节点编号
    q.push(ps);
    while(q.size()){
        int p=q.front();q.pop();
        if(tr[p].dep-tr[tr[p].top].dep<=kpl&&!tr[p].dfn){
            cnt++;tr[p].dfn=cnt;id[cnt]=p;if(kd[tr[p].top]==0) kd[tr[p].top]=p;
            if(tr[kd[tr[p].top]].dep-tr[tr[p].top].dep<tr[p].dep-tr[tr[p].top].dep) kd[tr[p].top]=p; 
        }
        if(tr[p].dfn){
            ls[ps][tr[p].dep-tr[ps].dep]=min(tr[p].dfn,ls[ps][tr[p].dep-tr[ps].dep]);
            rs[ps][tr[p].dep-tr[ps].dep]=max(rs[ps][tr[p].dep-tr[ps].dep],tr[p].dfn);
        }
        if(tr[p].dep-tr[ps].dep==kpl) continue;
        for(int i=0;i<s[p].size();i++){
            int y=s[p][i];if(tr[p].fa==y) continue;
            q.push(y);
        }
    }
}
void dfs2(int p,int fa){//修改BFS序的节点编号
    ls1[p]=cnt+1;bfs(p);
    for(int i=0;i<s[p].size();i++){int y=s[p][i];if(y==fa) continue;dfs2(y,p);}
    rs1[p]=cnt;
}
int ls2[100005],rs2[100005];
void dfs3(int p){//修改DFS序的节点编号
    ls2[p]=cnt+1;
    if(!tr[p].dfn) cnt++,tr[p].dfn=cnt,id[cnt]=p;
    if(tr[p].son) dfs3(tr[p].son);
    for(int i=0;i<s[p].size();i++){
        int y=s[p][i];if(y==tr[p].fa||y==tr[p].son) continue;
        dfs3(y);
    }
    rs2[p]=cnt;
}

领域修改：

void gailin(int x,int num){
    while(num>=0){
        if(ls[x][num]<=rs[x][num]) xiugai(1,ls[x][num],rs[x][num]);
        if(v[tr[x].top].size()-(tr[x].dep-tr[tr[x].top].dep)>num){
            int y=v[tr[x].top][(tr[x].dep-tr[tr[x].top].dep+num)];
            if(tr[y].dep>tr[kd[tr[x].top]].dep){xiugai(1,tr[y].dfn,tr[y].dfn);}
        }
        num--;
        if(num>=0){
            if(ls[x][num]<=rs[x][num])xiugai(1,ls[x][num],rs[x][num]);
            if(v[tr[x].top].size()-(tr[x].dep-tr[tr[x].top].dep)>num){
                int y=v[tr[x].top][(tr[x].dep-tr[tr[x].top].dep+num)];
                if(tr[y].dep>tr[kd[tr[x].top]].dep){xiugai(1,tr[y].dfn,tr[y].dfn);}
            }
        }
        x=tr[x].fa;if(x==0) num--,x=1;
    }
}

路径修改：

void gailian(int x,int y){
    while(tr[x].top!=tr[y].top){
        if(tr[tr[x].top].dep<tr[tr[y].top].dep) swap(x,y);
        if(tr[x].dep>tr[kd[tr[x].top]].dep){
            xiugai(1,tr[x].dfn-(tr[x].dep-tr[kd[tr[x].top]].dep-1),tr[x].dfn);
            x=kd[tr[x].top];
        }
        while(x!=tr[x].top){xiugai(1,tr[x].dfn,tr[x].dfn);x=tr[x].fa;}
        xiugai(1,tr[x].dfn,tr[x].dfn);
        x=tr[x].fa;
    }
    if(tr[x].dep>tr[y].dep) swap(x,y);
    if(tr[y].dep<=tr[kd[tr[y].top]].dep){
        while(y!=x){xiugai(1,tr[y].dfn,tr[y].dfn);y=tr[y].fa;}
        xiugai(1,tr[y].dfn,tr[y].dfn);return;
    }
    if(tr[x].dep>tr[kd[tr[x].top]].dep){xiugai(1,tr[x].dfn,tr[y].dfn);return;}
    xiugai(1,tr[y].dfn-(tr[y].dep-tr[kd[tr[y].top]].dep-1),tr[y].dfn);
    y=kd[tr[y].top];
    while(y!=x){xiugai(1,tr[y].dfn,tr[y].dfn);y=tr[y].fa;}
    xiugai(1,tr[y].dfn,tr[y].dfn);return;
}

子树修改：

void gaizi(int x){
    if(x!=1){
        for(int i=0;i<kpl;i++){
            if(ls[x][i]<=rs[x][i]){
                xiugai(1,ls[x][i],rs[x][i]);
            }
        }
    }
    if(ls1[x]<=rs1[x])xiugai(1,ls1[x],rs1[x]);
    if(ls2[x]<=rs2[x]) xiugai(1,ls2[x],rs2[x]);
}

查询的话同理可得。