题解：P3258 [JLOI2014] 松鼠的新家

· · 题解

这道题目让我们来详细讲一讲树上差分吧。

前置知识

基础差分，模板题点这。\ 最近公共祖先，模板题点这。

算法介绍

解决问题类型

在一棵树上有两个点 u 和 v，每个点都有自己的点权，需要把在 u 到 v 的这条简单路径上包含的所有的点的点权同时加上 z 或者减少 z。

这就是树上差分主要解决的问题。

实现

容易想到暴力，但是这样暴力修改点权的时间复杂度过高，所以不可取，这下，树上差分就派上用场了（别说什么线段树，树状数组，我不会）。

首先，能写到这题的人肯定已经学会了差分，如果不会请移步模板题。

这里的差分实现主要用图片来解释。

有这么一棵树（每个点旁边的数代表这个点的点权）：

现在接到任务，要把 4 到 8 的简单路径上的所有点（包含 4 和 8）的点权加 1，问现在每个点的点权。

记 cf_i 为点 i 与点 i-1 的点权差值。

我们先将 4 到根结点，8 到根结点中的点的点权全部加 1，用代码来表示为：

cf[u]++;
cf[v]++;

修改完的结果如下：

我们发现，结果并不是很理想。
问题出在这么几个地方：

我们先试着解决第一个问题，想到的方法是从 3 开始，先把到后面的所有点的点权减去 1，用代码表示为：

int lc = lca(u, v);
//lc存储u和v的最近公共祖先
cf[lc]--;

修改完后：

可以发现，第一个问题已经解决了，此时还剩下的问题：

那么我们如法炮制，从 3 的父亲开始，把到后面的所有点的点权减去 1，用代码表示为：

int lc = lca(u, v);
//f[i][j] 表示点i往上跳2^j次会到哪
cf[f[lc][0]]--;

现在修改完后变成了这样：

最后就是这样：

现在是不是没有问题了，那么恭喜你被我恭喜到了学会了树上差分！

树上差分的优点

在实现上，简单，方便。
在时间上，时间复杂度低，每次修改复杂度为 O(1)。

树上差分的注意事项

要用差分数组来求出原序列时，可以用搜索的方法。
设点 x 的孩子为 y，则求出 cf_x 的代码为：

cf[x] = cf[x] + cf[y];

需要注意：这一部分代码应该写在搜索的回溯时，要等 cf_y 更新完了才能求出正确的 cf_x。

树上差分例题

P3128
P3258

切入正题

这道题目想让我们干什么？其实就是把 u 到 v 的路径上的点的点权增加 1。

不过，需要注意的是，一个点 x 可能既能作为上次参观的终点，也可能是下次参观的起点，需要避免重复。
并且，最后一个房间不用给糖果。

学会了树上差分，这题就很简单了。

代码

终于要结束了（相信你们也看累了）。
最近公共祖先的部分就不打注释了，不会的见模板题。

#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 5;
int n, dq[N], cf[N], cg[N], dep[N], f[N][18], lg[N], maxd, maxdq = -1;
vector <int> ed[N];
void dfs(int x, int fa){
    dep[x] = dep[fa] + 1;
    f[x][0] = fa;
    if(dep[x] > maxd) maxd = dep[x];
    for(int i = 0;i < ed[x].size();i++){
        int tod = ed[x][i];
        if(tod != fa){
            dfs(tod, x);
            cf[x] += cf[tod];
        }
    }
}
void qcf(int x, int fa){
    for(int i = 0;i < ed[x].size();i++){
        int tod = ed[x][i];
        if(tod != fa){
            dfs(tod, x);
            cf[x] += cf[tod];
        }
    }
}
int lca(int u, int v){
    if(dep[u] < dep[v]) swap(u, v);
    while(dep[u] > dep[v]){
        u = f[u][lg[dep[u] - dep[v]]];
    }
    if(u == v) return u;
    for(int i = lg[dep[u] - 1];i >= 0;i--){
        if(f[u][i] != f[v][i]){
            u = f[u][i], v = f[v][i];
        }
    }
    return f[u][0];
}
int main(){
    scanf("%d", &n);
    for(int i = 1;i <= n;i++){
        scanf("%d", &cg[i]);
    }
    for(int i = 1;i < n;i++){
        int x, y;
        scanf("%d%d", &x, &y);
        ed[x].push_back(y);
        ed[y].push_back(x);
    }
    dfs(1, 0);
    for(int i = 2;i <= n;i++) lg[i] = lg[i / 2] + 1;
    for(int j = 1;j <= lg[maxd];j++){
        for(int i = 1;i <= n;i++){
            f[i][j] = f[f[i][j - 1]][j - 1];
        }
    }
    //树上差分的部分 
    for(int i = 1;i < n;i++){
        int x = cg[i], y = cg[i + 1], lc;
        lc = lca(x, y);
        cf[x]++, cf[y]++;
        cf[lc]--, cf[f[lc][0]]--;
    }
    qcf(1, 0);
    //要注意避免重复 
    for(int i = 2;i <= n;i++){
        cf[cg[i]]--;
    }
    for(int i = 1;i <= n;i++){
        printf("%d\n", cf[i]);
    }
    return 0;
}