Ariasakaの小窝

「JLOI2014」松鼠的新家

前言

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

传送门：

前往以下网站，不保证安全性哦喵~[JLOI2014] 松鼠的新家洛谷

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

解析

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

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

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

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

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

CPP

diff[u]++,diff[f[v][0]]++,diff[lca(u,v)]--,diff[f[lca(u,v)][0]]--;

代码

有注释版

CPP

#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;
}

无注释版

C++

#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;
}

洛谷 P3258 [JLOI2014] 松鼠的新家题解

此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。原文来自 — 版权归原作者所有。

推荐订阅源

Ariasakaの小窝

「JLOI2014」松鼠的新家

前言

解析

代码

有注释版

无注释版