题解 1654G Snowy Mountain
pengyule
2022-04-13 21:42:01
[1654G Snowy Mountain](http://codeforces.com/problemset/problem/1654/G)
> 一棵 $n(n\le 2\cdot 10^5)$ 个点的树，布尔数组 $l_i$ 表示点 $i$ 是不是基地，一个点的高度 $h_i$ 为其到最近的基地的距离。从一个点出发时动能为 $0$，随后可以下滑或走平地，从 $u$ 到相邻的 $v$：若 $h_u>h_v$，则增加 $1$ 动能，若 $h_u=h_v$，则减少 $1$ 动能。问从每个点出发、全程动能非负最远可以到的距离。
滑雪下来重力势能做的功是恒定的，我们实际要最大化产生的热能，即滑更多的平地。
**结论1**（贪心）最优策略为滑到一个海拔最低的“辗转点”，再在这个平台上辗转直到动能耗尽，再由它径直滑到最近的基地。*定义“辗转点”为相邻节点中有与它等高的点的点。*
*证明*：当人到达终点时，具有动能 $w$，$w$ 就是完全被浪费的，原因是除掉恒定的那 $h_u$ 个单位长度，没有浪费的机械能都会转化为一单位热能，即一单位长度，要最小化浪费，就要最低化目标“辗转点”。进一步量化，令 $h_u,h_v$ 为起始点和目标“辗转点”的高度，$len$ 表示路径总长度，则根据上面有 $len=h_u+(h_u-h_v)=2h_u-h_v$。
现在的任务变为求一个点能到达的最低“辗转点”。
**结论2** 所有“辗转点”的高度总和为 $O(n)$ 级别。
*证明*：
**推论** 高度不同的“辗转点”数量不超过 $\sqrt{2n}=O(\sqrt n)$。（最坏情况下是 $\sum h=1+2+...$）
这就是说我们可以暴力枚举辗转平台高度，并看看哪些点可以到达这一高度的辗转点的任意一个，更新它们的答案。
具体地，我们设 $c_u$ 为 $u$ 到达任何一个这一高度的辗转点的最小初始动能，则扩展 $c_u$ 的过程等价于在一个边权为 $h_u=h_v\to 1$、$h_u<h_v\to-1$ 的图上跑多源最短路；这个可以使用分层 bfs，将高度相同的点视作同一层，按高度从小到大处理每一层：在层内部做普通的 bfs（一个点可能会多次入队，但所有点的入度之和是 $O(n)$ 的），搞完后进行 $h\to h+1$ 的边的扩展。总时间复杂度 $O(n\sqrt n)$。
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5,INF=0x3f3f3f3f;
int n,l[N],h[N],u[N],v[N],c[N],mn[N];
vector<int>G[N],nd[N],land[N];
queue<int>Q;
inline int read(){
register char ch=getchar();register int x=0;
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return x;
}
void bfs(int H){
memset(c,0x3f,sizeof(c));
for(int i=0;i<land[H].size();i++)c[land[H][i]]=0;
for(int i=H;i<=n;i++){
for(int j=0;j<nd[i].size();j++)if(c[nd[i][j]]!=INF)Q.push(nd[i][j]);
while(!Q.empty()){
int x=Q.front();Q.pop();
for(int j=0;j<G[x].size();j++){
int y=G[x][j];
if(h[x]!=h[y])continue;
if(c[x]+1<c[y]){
c[y]=c[x]+1;
Q.push(y);
}
}
}
for(int j=0;j<nd[i].size();j++)if(c[nd[i][j]]!=INF){
int x=nd[i][j];
for(int k=0;k<G[x].size();k++){
int y=G[x][k];
if(h[x]<h[y]&&c[x]-1<c[y]){
c[y]=max(c[x]-1,0);
}
}
}
}
for(int i=1;i<=n;i++)if(!c[i])mn[i]=min(mn[i],H);
}
int main(){
n=read();
memset(h,-1,sizeof(h));
for(int i=1;i<=n;i++){
l[i]=read();
if(l[i])h[i]=0,Q.push(i);
}
for(int i=1;i<n;i++)u[i]=read(),v[i]=read(),G[u[i]].push_back(v[i]),G[v[i]].push_back(u[i]);
while(!Q.empty()){
int x=Q.front();Q.pop();
for(int i=0;i<G[x].size();i++){
int y=G[x][i];
if(h[y]==-1)h[y]=h[x]+1,Q.push(y);
}
}
for(int i=1;i<=n;i++)nd[h[i]].push_back(i);
for(int i=1;i<=n;i++){
bool flag=0;
for(int j=0;j<G[i].size();j++)if(h[G[i][j]]==h[i]){flag=1;break;}
if(flag)land[h[i]].push_back(i);
}
for(int i=1;i<=n;i++)mn[i]=h[i];
for(int i=0;i<=n;i++)if(land[i].size())bfs(i);
for(int i=1;i<=n;i++)cout<<(mn[i]==INF?0:2*h[i]-mn[i])<<' ';
}
```