题目大意

有一棵 $n$ 个节点的有根树，根为节点 $0$。某些节点上有赛车，每秒每辆赛车向父节点移动。如果在非根节点上同时有多辆赛车，它们会相撞并退出比赛。对于每个节点 $v$：

• 如果 $v$ 没有赛车：输出 $-1$
• 如果 $v$ 的赛车在途中相撞：输出 $-1$
• 否则：输出到达根节点的时间

解题思路

关键观察

1. 碰撞条件：两辆赛车在非根节点 $u$ 相撞，当且仅当它们在同一时刻到达 $u$
2. 到达时间：从节点 $v$ 到根节点的时间就是 $v$ 的深度
3. 碰撞检测：如果某个节点 $u$ 有多于 1 辆赛车在同一时刻到达，那么这些赛车都会相撞

核心思想

我们可以从叶子节点向根节点进行 BFS 或 DFS，统计每个节点上"可能到达"的赛车数量。

具体步骤：

1. 计算每个节点的深度
2. 对于有赛车的节点，记录它的深度（即到达时间）
3. 从叶子节点开始向上传递信息：
   • 如果一个节点有多个来自不同子树的赛车在同一深度到达，那么这些赛车会相撞
   • 只有那些"唯一"到达某个节点的赛车才能继续向上移动

算法实现

1. 建树：根据输入的父亲关系建立树结构
2. 计算深度：DFS 或 BFS 计算每个节点到根的距离
3. 处理赛车：
   • 初始化答案数组为 $-1$
   • 对于有赛车的叶子节点，暂时记录其深度为答案
   • 从下向上处理：如果某个节点有多个子节点在同一深度传来赛车，则这些赛车相撞
   • 只有那些"幸存"的赛车才能继续向上传递

时间复杂度

• 建树：$O(n)$
• DFS/BFS：$O(n)$
• 总复杂度：$O(n)$

代码实现

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n;
    cin >> n;
    
    vector<int> parent(n);
    vector<vector<int>> children(n);
    
    // 读入父亲关系并建立树
    for (int i = 1; i < n; i++) {
        cin >> parent[i];
        children[parent[i]].push_back(i);
    }
    
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    
    // 计算深度
    vector<int> depth(n, 0);
    for (int i = 1; i < n; i++) {
        depth[i] = depth[parent[i]] + 1;
    }
    
    // 答案数组
    vector<int> ans(n, -1);
    
    // 记录每个节点上"可能到达"的赛车的深度
    vector<map<int, int>> cnt(n);
    
    // 从叶子节点开始向上处理
    for (int i = n - 1; i >= 0; i--) {
        if (a[i] == 1) {
            // 该节点有赛车
            cnt[i][depth[i]]++;
        }
        
        // 将当前节点的信息传递给父节点
        if (i > 0 && !cnt[i].empty()) {
            auto it = cnt[i].begin();
            if (it->second == 1) {
                // 只有一辆赛车以这个深度到达，可以继续向上
                cnt[parent[i]][it->first]++;
            }
            // 如果有多辆赛车以相同深度到达，它们相撞，不向上传递
        }
    }
    
    // 设置答案
    for (int i = 0; i < n; i++) {
        if (a[i] == 0) {
            ans[i] = -1;
        } else {
            // 检查这辆赛车是否幸存
            bool survive = true;
            int cur = i;
            int d = depth[i];
            
            while (cur > 0) {
                if (cnt[cur][d] > 1) {
                    survive = false;
                    break;
                }
                cur = parent[cur];
                d--;
            }
            
            if (survive) {
                ans[i] = depth[i];
            } else {
                ans[i] = -1;
            }
        }
    }
    
    // 优化：更高效的实现方式
    // 重新初始化答案
    fill(ans.begin(), ans.end(), -1);
    
    // 使用DFS从下向上处理
    function<void(int)> dfs = [&](int u) {
        map<int, int> merge;
        
        for (int v : children[u]) {
            dfs(v);
            // 合并子节点的信息
            for (auto [d, c] : cnt[v]) {
                merge[d] += c;
            }
        }
        
        if (a[u] == 1) {
            merge[depth[u]]++;
        }
        
        // 移除相撞的赛车（数量大于1的深度）
        for (auto it = merge.begin(); it != merge.end(); ) {
            if (it->second > 1) {
                it = merge.erase(it);
            } else {
                ++it;
            }
        }
        
        cnt[u] = move(merge);
    };
    
    dfs(0);
    
    // 设置最终答案
    for (int i = 0; i < n; i++) {
        if (a[i] == 1 && cnt[i].count(depth[i])) {
            ans[i] = depth[i];
        }
    }
    
    // 输出答案
    for (int i = 0; i < n; i++) {
        cout << ans[i] << (i == n - 1 ? "\n" : " ");
    }
    
    return 0;
}

样例分析

对于样例：

5
0 1 1 3
0 1 1 1 1

树结构：

0
└── 1
    ├── 2
    └── 3
        └── 4

• 节点 0：无赛车，输出 -1
• 节点 1：有赛车，深度 1，能到达根，输出 1
• 节点 2：有赛车，但在节点 1 与节点 1 的赛车相撞，输出 -1
• 节点 3：有赛车，但在节点 1 与其他赛车相撞，输出 -1
• 节点 4：有赛车，深度 3，能到达根，输出 3

总结

这道题的关键在于理解赛车相撞的条件，以及如何高效地检测这些碰撞。通过从叶子节点向上传递信息，我们可以确定哪些赛车能够安全到达根节点。算法的时间复杂度是线性的，能够处理 $n \leq 10^6$ 的大数据规模。