自动搬运

查看原文

来自洛谷，原作者为

	SamHJD .

搬运于2025-08-24 23:04:49，当前版本为作者最后更新于2024-10-08 19:23:12，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

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

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

$$f_u= \begin{cases} 1 \qquad \sum_v f_v=1\\ 0 \qquad \text{otherwise} \end{cases} $$

尝试树上启发式合并同时处理不同的深度。记 $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;
}