题解 1654G Snowy Mountain

· · 题解

1654G Snowy Mountain

一棵 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)。

#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])<<' ';
}