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

· · 题解

这道题我去年就听过了，但直到现在才做出来。

这道题明显可以用 树剖+线段树 做。

但是我们也可以用时间复杂度更低的 LCA+树上差分 做。

LCA

LCA 中文名：最近公共祖先。

正如 LCA 的名字，LCA 就是树上两个点的公共祖先中距离这两点距离最近的祖先。

显然通过 LCA 是可以求树上两点的最短距离。

在上面这棵树中：

. . . . . .

求 LCA 常用的有两种：

我通常用第 2 种（当然，在这里感谢 @StarsIntoSea_SY）

所以我就主要说第二种了：

树链剖分求 LCA

首先 ，你要先学会 树链剖分。

初始化就不讲了，大家肯定都会了

注意，我这里讲的是重链剖分

还是上面那个图，我们求编号 4 的点和编号 3 的点的 LCA：

1.

我们比较编号为 4 的点所在链的顶端的深度和编号为 3 的点所在链的顶端的深度。

显然编号为 4 的点所在链的顶端的深度更大，于是我们就从编号为 4 的点跳到编号为 2 的点（即跳到编号为 4 的点所在链的顶端的父亲）。

那我们想想为什么要跳深度更深的点呢？

那我们可以看一下，如果我们不跳 4 而跳 3 的话，那么就跳到 1 的父亲了，那肯定是不对的。

2.

我们比较编号为 2 的点所在链的顶端的深度和编号为 3 的点所在链的顶端的深度。

显然编号为 3 的点所在链的顶端的深度更大，于是我们就从编号为 3 的点跳到编号为 1 的点（即跳到编号为 3 的点所在链的顶端的父亲）。

3.

此时，我们发现编号为 1 的点与编号为 2 的点是在同一条链上的，那么就不能再跳了，而是比较这两点的深度，深度小的点就是 LCA。

这样我们就得到了编号 4 的点和编号 3 的点的 LCA。

LCA 好题：

P3379 【模板】最近公共祖先（LCA）

P3128 [USACO15DEC] Max Flow P

P3258 [JLOI2014] 松鼠的新家

很多树链剖分的题需要 LCA ，所以也可以刷树剖的题。

树上差分

学树上差分，你肯定需要先学会差分。

差分

差分其实也利用了前缀和的思想。

一个问题：

给你长为 n 的序列 a，有 m 次操作，每次操作会指定一个区间 [ l,r ] 将区间范围内的数加 1 ，问 m 次操作后的序列。

显然这道题可以用暴力来做，但是我们如果把 n，m 开的很大那么暴力也只会 TLE。

于是，我们就来用差分。

先定义一个差分数组 f ，第 i 个数表示 a[i] - a[i-1]，你应该猜测出它的作用了吧。

然后，每次操作时就把左端点在 f 数组中 +1 ，而把右端点的下一个数在 f 数组中 -1。（最好自己亲身模拟一下）

这样，我们求第 i 个数的值时，只需要求出：

f[1] + f[2] + f[3]+...+f[i]

的值就行了。

差分好题：

P2367 语文成绩

P1672 [USACO05FEB] Feed Accounting S

P4231 三步必杀

P4868 Preprefix sum

树上差分

会了差分，其实树上差分也没有什么难的。

还是这张图，我们来看看树上差分的过程。

假设，我们要把从 4 到 6 的最短路径中的每个点的值加 1。

首先，我们得先知道从 4 到 6 的最短路径是哪条：

红色的那条其实就是从 4 到 6 的最短路径。

那么我们怎样实现呢？

首先，跟差分一样，我们也定义一个数组 d ，但在这里，它并不表示差。

然后，我们将 d[4] 和 d[6] 都 +1。

再把 d[LCA(4,6)] 和 d[fa[LCA(4,6)] 都 -1。

（LCA 表示 LCA，fa是存父亲的数组）

这样我们在求答案时，第 i 个点的值就是把它子树里的节点的 d 数组值相加在加上 d[i] 就行了。

树上差分:

\begin{cases}d[x] + 1 \\d[y] + 1\\d[ lca(x,y) ]-1\\d[fa[ lca (x,y) ]]-1\end{cases}

常见问题

为什么要 d[ lca(x,y) ]-1

因为我们加时 d[ lca(x,y) ] 加了两次，要减掉一次。

为什么要d[fa[ lca (x,y) ]]-1

因为 fa[ lca(x,y) ] 的答案是要加上 d[ lca(x,y) ] 的，但是从 x 到 y 的最短路径不包括它所以要减去，同时它的祖先也就不会受影响。

树上差分好题：

P3258 [JLOI2014] 松鼠的新家

P3128 [USACO15DEC] Max Flow P

差分、树上差分的题单

回归题目

我们发现，它不就是一道裸题吗？

于是你高高兴兴的打完后发现：

唉？样例怎么不过。

其实这道题有两个坑点：

#include<bits/stdc++.h>
using namespace std;
int n;
int cnt;
struct node{
    int to,nxt;
}z[10000004];
struct nod{
    int dep,fa,top,son,maxxson,num;
}l[10000003];
int h[10000004];
int d[10000004];
int a[10000004];
void add(int x,int y){
    z[++cnt].to=y;
    z[cnt].nxt=h[x];
    h[x]=cnt;
}
void dfs(int x,int fa){
    l[x].fa=fa;
    l[x].dep=l[fa].dep+1;
    l[x].son=1;
    l[l[x].maxxson].son=-1;
    for(int i=h[x];i;i=z[i].nxt){
        int y=z[i].to;
        if(y==fa) continue;
        else{
            dfs(y,x);
            l[x].son+=l[y].son;
            if(l[y].son>l[l[x].maxxson].son){
                l[x].maxxson=y;
                l[l[x].maxxson].son=l[y].son;
            } 
        }
    }
}
int num;
void dfs1(int x,int fa,int top){
    l[x].num=++num;
    l[x].top=top;
    if(!l[x].maxxson) return ;
    else{
        dfs1(l[x].maxxson,x,top);
        for(int i=h[x];i;i=z[i].nxt){
            int y=z[i].to;
            if(y==fa||y==l[x].maxxson) continue;
            else{
                dfs1(y,x,y);
            }
        }
    }
}
int lca(int a,int b){
    while(l[a].top!=l[b].top){
        if(l[l[a].top].dep<l[l[b].top].dep){
            swap(a,b);
        }
        a=l[l[a].top].fa;
    }
    if(l[a].dep>l[b].dep) swap(a,b);
    return a;
}
int ans;
void Dfs(int x,int fa){
    for(int i=h[x];i;i=z[i].nxt){
        int y=z[i].to;
        if(y==fa) continue;
        Dfs(y,x);
        d[x]+=d[y];
    }
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<n;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);
        add(y,x);
    }
    l[0].dep=0;
    dfs(1,0);
    dfs1(1,0,1);
    for(int i=1;i<n;i++){
        int lcA=lca(a[i],a[i+1]);
        d[a[i]]++;
        d[a[i+1]]++;
        d[lcA]--;
        d[l[lcA].fa]--;
    }
    Dfs(1,0);
    for(int i=2;i<=n;i++){
        d[a[i]]--;
    }
    for(int i=1;i<=n;i++){
        printf("%d\n",d[i]);
    }
}