题解：P17307 [ICPC 2026 Xi'an I] Zebra Crossing

· · 题解

题意简述

给定一棵黑白染色的树。

每次可以跳到距离不超过 k 的任意节点。 对每个 i\geq 2，求从 1 到 i 时， 最少需要落在多少个黑点上。

解题思路

固定一个终点 x，考虑从 1 到 x 的简单路径。 把跳跃看成沿这条路径逐边推进， 并维护当前一次跳跃还能前进多少条边。

设已经到达路径上的节点 u，剩余距离为 r。 若不改变落点，当前状态自然可以继续保留。 除此以外，还可以借助树中的白点更新状态。

设上一次落点为 p，并且从 p 推进到 u 已经消耗了 k-r 的距离。 若存在白点 w 满足 \operatorname{dist}(u,w)=d\leq r，则有：

\operatorname{dist}(p,w)\leq k-r+d\leq k

因此可以把本次跳跃的落点改成 w。 落在白点上没有代价，且下一次跳跃重新拥有 k 的距离。 从 w 回到 u 需要消耗 d， 所以回到 u 后还剩 k-d。

只需知道每个节点到最近白点的距离。 令该距离为 d_u，可以从所有白点同时开始 BFS 求出。 在节点 u 能借助白点时，状态转移为：

r\gets\max(r,k-d_u)

这里选择最近白点最优，因为它使 k-d_u 最大。 对已经支付相同黑点代价的两个状态， 剩余距离更大的状态能完成另一状态的所有后续跳跃， 所以只保留最大的剩余距离即可。

接下来以 1 为根遍历整棵树。 对父子边 u\to v，先把剩余距离减一。 若 d_v 不超过当前剩余距离， 就按照上述方法尝试借助最近白点。

若更新后剩余距离仍为零， 说明这次跳跃已经走满 k 条边，且无法落在白点上。 此时必须支付一次黑点代价。 落在当前节点不会比落在其他黑点更差， 因为绕到树外的黑点只会额外消耗下一次跳跃的距离。 支付代价后，把剩余距离重置为 k。

遍历到目标节点时，目标本身也必须成为最后一次跳跃的落点。 若剩余距离已经重置为 k， 说明刚好在目标处强制落地，代价已经统计。 否则只需在目标为黑点时再增加一次代价。

多源 BFS 和树上遍历均为 O(n)，空间复杂度为 O(n)。

参考代码

#include <bits/stdc++.h>
using namespace std;

const int N=500005;
const int inf=0x3f3f3f3f;
vector<int> G[N];
int dis[N],fa[N],len[N],f[N],que[N];
void solve()
{
    int n,k;
    cin>>n>>k;
    string s;
    cin>>s;
    for(int i=1;i<=n;i++)
    {
        G[i].clear();
        dis[i]=inf;
    }
    for(int i=1;i<n;i++)
    {
        int u,v;
        cin>>u>>v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    int l=1,r=0;
    for(int i=1;i<=n;i++)
    {
        if(s[i-1]=='1')
        {
            dis[i]=0;
            que[++r]=i;
        }
    }
    while(l<=r)
    {
        int u=que[l++];
        for(auto v:G[u])
        {
            if(dis[v]==inf)
            {
                dis[v]=dis[u]+1;
                que[++r]=v;
            }
        }
    }
    l=r=1;
    que[1]=1;
    fa[1]=0;
    len[1]=k;
    f[1]=0;
    while(l<=r)
    {
        int u=que[l++];
        for(auto v:G[u])
        {
            if(v==fa[u])continue;
            fa[v]=u;
            f[v]=f[u];
            len[v]=len[u]-1;
            if(dis[v]<=len[v])len[v]=max(len[v],k-dis[v]);
            if(len[v]==0)
            {
                f[v]++;
                len[v]=k;
            }
            que[++r]=v;
        }
    }
    for(int i=2;i<=n;i++)
    {
        if(i>2)cout<<' ';
        cout<<f[i]+(len[i]!=k&&s[i-1]=='0');
    }
    cout<<'\n';
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin>>T;
    while(T--)solve();
    return 0;
}