题解：P11162 「BalkanOI 2023 Day1」Car Race

SamHJD · 2024-10-08 19:23:12 · 题解

首先，由于每次将所有赛车的深度均减一，因此相撞的车深度一定相同。

考虑一个 O(n^2) 的 dp，每次对深度相同的车进行。对于一个深度 d，容易发现除了根以外的节点 u 最多有一个深度为 d 的车到达，于是设 f_u 表示是否有深度为 d 的点到达 u，枚举 u 的子节点，转移如下：

尝试树上启发式合并同时处理不同的深度。记 b_i 表示 i 车是否会被撞，开一个桶 now 记录每个深度能走到当前节点的点的编号。

同一般的启发式合并，先递归子节点处理 b，重儿子的 now 信息不删除。接着枚举所有轻儿子的子树中的节点，若某节点能顺利走到其所在子树的根，即 b_u 不为真，则将其放入 now 中。若 now 中某一深度放入了大于 1 个点，则这些点都会相撞，更新 b。

注意走到根的车不会相撞，需要从根的每个子节点递归。

/*

下面代码中若 now[i] 中放入了大于 1 个点则将 now[i] 设为 -1
由于这个 -1 只对于当前的子树，因此轻重儿子计算完后均需要将 -1 的位置更改为 0

*/

#include <bits/stdc++.h>
#define rep(i,k,n) for(int i=k;i<=n;++i)
#define per(i,n,k) for(int i=n;i>=k;--i)
using namespace std;
template<typename T>
inline void read(T &x){
    x=0;int f=1;char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
    for(;isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+(c-'0');
    x*=f;
}
const int N=1e6+10;
int T;
int n,l[N],siz[N],dep[N],son[N],dfn[N],id[N],tim,have[N];
vector<int> g[N];
void init(int u,int fa){
    dep[u]=dep[fa]+1;siz[u]=1;dfn[u]=++tim;id[tim]=u;
    int maxs=-1;
    for(auto v:g[u]){
        if(v==fa) continue;
        init(v,u);
        siz[u]+=siz[v];
        if(siz[v]>maxs) maxs=siz[v],son[u]=v;
    }
}
int broke[N],now[N];
vector<int> use,use_1;
void dfs(int u,int fa){
    for(auto v:g[u]){
        if(v==fa||v==son[u]) continue;
        dfs(v,u);
        for(auto uu:use) now[uu]=0;use.clear();
    }
    if(son[u]) dfs(son[u],u);
    if(u==1) return;
    if(have[u]) now[dep[u]]=u,use.push_back(dep[u]);
    for(auto v:g[u]){
        if(v==fa||v==son[u]) continue;
        rep(i,dfn[v],dfn[v]+siz[v]-1){
            int x=id[i];
            if(broke[x]||!have[x]) continue;
            else if(now[dep[x]]==-1) broke[x]=1;
            else if(now[dep[x]]){
                broke[now[dep[x]]]=1;
                now[dep[x]]=-1;use.push_back(dep[x]);
                use_1.push_back(dep[x]);
                broke[x]=1;
            }
            else now[dep[x]]=x,use.push_back(dep[x]);
        }
    }
    for(auto uu:use_1) now[uu]=0;use_1.clear();
}
void solve(){
    read(n);
    rep(i,2,n){
        int fa;read(fa);fa++;
        g[i].push_back(fa);
        g[fa].push_back(i);
    }
    rep(i,1,n) read(have[i]);
    init(1,0);
    dfs(1,0);
    rep(i,1,n){
        if(have[i]&&!broke[i]) printf("%d ",dep[i]-1);
        else printf("-1 ");
    }
}
int main(){
    T=1;while(T--) solve();
    return 0;
}