「JLOI2014」松鼠的新家
前言
这道题倒也不是很难，只是有一些小坑需要避一下，可以看作半个 LCA 树上差分裸题。
解析
考虑维护一个树，点 \(u\) 表示每个房间需要的糖果数 \(s_u\)，而维尼在参观房间时从 \(a\) 到 \(b\) 就需要在 \((a,\to b)\) 的路径上的每个房间都摆上一个糖果，这时直接使用树上差分来区间维护先前的那棵树即可。
树上差分不懂的可以看：https://qoj.fzoi.top/post/7315 。
这里求差分所用的 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\) 的父亲节点）范围内的增值就好了。
写成代码就是：
diff[u]++,diff[f[v][0]]++,diff[lca(u,v)]--,diff[f[lca(u,v)][0]]--;
代码
有注释版
#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;
}
无注释版
#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;
}