「JLOI2014」松鼠的新家

前言

最近在学校上课，不过还是用wexa传了博客（只是懒得放封面

传送门：

引用站外地址
[JLOI2014] 松鼠的新家
洛谷

这道题倒也不是很难，只是有一些小坑需要避一下，可以看作半个 LCA 树上差分裸题。

解析

考虑维护一个树，点 uu 表示每个房间需要的糖果数 sus_u，而维尼在参观房间时从 aa 到 bb 就需要在 (a,→b)(a,\to b) 的路径上的每个房间都摆上一个糖果，这时直接使用树上差分来区间维护先前的那棵树即可。

树上差分不懂的自行百度。

这里求差分所用的 LCA 采用了倍增的方式，总计时间复杂度为 O(nlog⁡n+n)O(n \log n+n)。

需要注意的坑是（不看一定会爆零的qwq：

  1. 输入格式，边在路径下面，需要把路径存下来。
  2. 这里的路径是一个数组，每次维护差分时实际上 u,vu,v 对应的是 pathi,pathi+1path_i,path_{i+1}。
  3. 因为每一次到一个房间时会更新 (u→v)(u\to v) 中的每个节点的差分值，当然包括了 uu 和 vv，那么你再出发时开始的 vv 又会被重复加上，而且最后一个房间是没有糖果的，所以只需要更新 (u→fa[v][0])(u\to fa[v][0]) （vv 的父亲节点）范围内的增值就好了。
    写成代码就是：
1
diff[u]++,diff[f[v][0]]++,diff[lca(u,v)]--,diff[f[lca(u,v)][0]]--;

代码

有注释版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <bits/stdc++.h>
using namespace std;
constexpr int maxn=3e5+5; //这样定义要快一点（c++11
vector<int> g[maxn]; //vector邻接表建图
int n,m,diff[maxn],dep[maxn],s[maxn],f[maxn][24],ans;
inline void add(int u,int v) {g[u].push_back(v);}
void pre(int u,int fa){
    dep[u]=dep[fa]+1,f[u][0]=fa; //预处理
    for(int i=0;i<20;i++)
        f[u][i+1]=f[f[u][i]][i];
    for(int v:g[u])
        if(v!=fa) pre(v,u);
}
int lca(int x,int y){
    if(dep[x]<dep[y]) swap(x,y); //倍增求LCA
    for(int i=20;i>=0;i--){
        if(dep[f[x][i]]>=dep[y]) x=f[x][i];
        if(x==y) return x;
    }
    for(int i=20;i>=0;i--)
        if(f[x][i]!=f[y][i])
            x=f[x][i],y=f[y][i];
    return f[x][0];
}
inline void dfs(int u,int fa){
    for(auto e:g[u]){ //回溯还原差分数组
        if(e==fa) continue;
        dfs(e,u),diff[u]+=diff[e];
    }
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>s[i]; //注意输入格式，坑1
    for(int i=1,x,y;i<n;i++)
        cin>>x>>y,add(x,y),add(y,x);
    pre(1,0);
    for(int i=1,x,y;i<n;i++) //维护方式，坑2 
        x=s[i],y=s[i+1],diff[x]++,diff[f[y][0]]++,  //坑3
        diff[lca(x,y)]--,diff[f[lca(x,y)][0]]--;
    dfs(1,0); //还原数组
    for(int i=1;i<=n;i++) cout<<diff[i]<<endl; //输出糖果数即可
    return 0;
}

无注释版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <bits/stdc++.h>
using namespace std;
constexpr int maxn=3e5+5;
vector<int> g[maxn];
int n,m,diff[maxn],dep[maxn],s[maxn],f[maxn][24],ans;
inline void add(int u,int v) {g[u].push_back(v);}
void pre(int u,int fa){
    dep[u]=dep[fa]+1,f[u][0]=fa;
    for(int i=0;i<20;i++)
        f[u][i+1]=f[f[u][i]][i];
    for(int v:g[u])
        if(v!=fa) pre(v,u);
}
int lca(int x,int y){
    if(dep[x]<dep[y]) swap(x,y);
    for(int i=20;i>=0;i--){
        if(dep[f[x][i]]>=dep[y]) x=f[x][i];
        if(x==y) return x;
    }
    for(int i=20;i>=0;i--)
        if(f[x][i]!=f[y][i])
            x=f[x][i],y=f[y][i];
    return f[x][0];
}
inline void dfs(int u,int fa){
    for(auto e:g[u]){
        if(e==fa) continue;
        dfs(e,u),diff[u]+=diff[e];
    }
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>s[i];
    for(int i=1,x,y;i<n;i++)
        cin>>x>>y,add(x,y),add(y,x);
    pre(1,0);
    for(int i=1,x,y;i<n;i++)
        x=s[i],y=s[i+1],diff[x]++,diff[f[y][0]]++,
        diff[lca(x,y)]--,diff[f[lca(x,y)][0]]--;
    dfs(1,0);
    for(int i=1;i<=n;i++) cout<<diff[i]<<endl;
    return 0;
}