G. Path Prefixes - 题解

比赛与标签

比赛: Codeforces Round 811 (Div. 3) 标签: binary search, data structures, dfs and similar, trees 难度: *1700

题目大意喵~

主人你好呀~ 这道题是关于一棵可爱的树的喵！(ฅ'ω'ฅ)

我们拿到的是一棵有 n 个节点的有根树，根节点是 1。树上的每一条边都有两个正整数权值，我们叫它们 a 和 b 好了。

对于除了根节点之外的每一个节点 i (从 2 到 n)，我们需要计算一个值 r_i。它的定义是这样的：

首先，我们找到从根节点 1 到节点 i 的唯一路径。计算这条路径上所有边的 a 权值之和，记为 A_i。
然后，我们要在这条 1 -> i 的路径上，从根节点 1 出发，找一个最长的前缀路径。这个“最长”的定义是：这个前缀路径上所有边的 b 权值之和，不能超过我们刚刚算出来的 A_i。
r_i 就是这个最长前缀路径的长度（也就是边的数量）。

最后，我们需要按顺序输出 r_2, r_3, ..., r_n。听起来是不是很有趣呐？

解题思路喵~

这道题要求我们处理从根节点到每个节点的路径信息，这种问题呀，用深度优先搜索（DFS）来解决再合适不过了喵！DFS可以很自然地遍历树上的每一条根到叶的路径。

让我们跟着DFS的脚步来思考一下。当我们从父节点 u 走到子节点 v 时，我们可以很轻松地维护从根到 v 的路径信息。具体来说：

A_i 的计算: 从根到 v 的 a 权值总和 A_v，就是从根到 u 的 a 权值总和 A_u 加上边 (u, v) 的 a 权值。这个可以在DFS过程中递推得到。
B_prefix 的计算: 同样，从根到路径上任意一点的 b 权值总和也可以递推。

现在，关键问题来了：当我们到达节点 i 时，如何快速找到那个最长的前缀路径呢？

这条从根 1 到 i 的路径上的节点，我们依次标记为 p_0, p_1, ..., p_k，其中 p_0=1, p_k=i。它们各自的 b 权值前缀和（从根到该点的 b 值总和）我们记为 B_{p_0}, B_{p_1}, ..., B_{p_k}。

一个重要的发现喵！ 因为题目保证了每条边的 b 权值都是正数，所以这些 b 的前缀和 B_{p_0}, B_{p_1}, ..., B_{p_k} 一定是单调递增的！

既然是单调递增的序列，那我们想在里面找一个不超过 A_i 的最大值，不就可以用二分查找（Binary Search）了嘛！(๑•̀ㅂ•́)و✧

所以，我们的整体策略就清晰啦：

DFS 遍历: 从根节点 1 开始进行深度优先搜索。
维护路径信息: 在DFS的过程中，我们用一个动态数组（vector）来记录当前路径上所有节点的 b 权值前缀和。我们叫它 path_b 吧。当进入一个新节点 v 时，我们将它的 b 前缀和 B_v 加入 path_b 的末尾。当离开节点 v（回溯）时，再把它从末尾移除。这样 path_b 就始终精确地反映了当前从根到当前节点的路径信息。
二分查找求解: 每当我们访问到一个节点 i，我们就拿到了它的 A_i 值。此时，我们在 path_b 这个有序数组里进行二分查找，找到最后一个不大于 A_i 的元素。
计算结果: C++ 的 std::upper_bound 函数能帮我们找到第一个大于 A_i 的元素的位置。那么它前面的那个位置，就是我们想要的最后一个不大于 A_i 的元素啦。这个位置的索引（从0开始）就等于满足条件的路径前缀的节点数减一，恰好就是我们要求的路径长度 r_i！

举个例子：如果 path_b 是 [0, 6, 16]，A_i 是 14。upper_bound 会找到 16。它的索引是 2。那么答案就是 2 - 1 = 1。这表示长度为 0 和 1 的前缀都满足条件，最长的是 1。完美~

代码实现上，为了防止树太深导致递归栈溢出，我们可以用一个栈（Stack）来手动模拟DFS的过程，这样会更稳健一些的说。

代码实现喵~

cpp

// 完整的AC代码，添加详细注释解释关键逻辑
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#include <tuple> // 别忘了包含tuple头文件喵~

using namespace std;

void solve() {
    int n;
    cin >> n;

    // 使用邻接表来存储树的结构，每个边包含三个信息：子节点、a值、b值
    vector<vector<tuple<int, long long, long long>>> graph(n + 1);
    for (int i = 2; i <= n; i++) {
        int p;
        long long a, b;
        cin >> p >> a >> b;
        graph[p].emplace_back(i, a, b);
    }

    // total_a[i] 存储从根到节点i的a值总和
    vector<long long> total_a(n + 1, 0);
    // total_b[i] 存储从根到节点i的b值总和
    vector<long long> total_b(n + 1, 0);
    // next_index[u] 用于迭代式DFS，记录节点u的下一个要访问的子节点索引
    vector<int> next_index(n + 1, 0);
    
    // path_b 存储当前DFS路径上，从根到每个节点的b值前缀和
    vector<long long> path_b;
    path_b.push_back(0); // 根节点的前缀和是0，路径长度为0

    // st 是我们用来模拟DFS的栈
    stack<int> st;
    st.push(1); // 从根节点1开始

    vector<int> ans_arr(n + 1, 0);

    // 迭代式DFS主循环
    while (!st.empty()) {
        int u = st.top();

        // 如果当前节点u还有未访问的子节点 (这是DFS的“前进”部分)
        if (next_index[u] < graph[u].size()) {
            // 获取下一个子节点v和对应的边权
            auto [v, a_val, b_val] = graph[u][next_index[u]];
            next_index[u]++; // 更新索引，下次访问u时就从下一个子节点开始

            // 计算到达v的a值和b值总和
            total_a[v] = total_a[u] + a_val;
            total_b[v] = total_b[u] + b_val;
            
            // 将v的b值总和加入当前路径的记录中
            path_b.push_back(total_b[v]);

            // 核心步骤：在当前路径的b值前缀和序列中，进行二分查找
            // upper_bound 找到第一个 > total_a[v] 的元素
            auto it = upper_bound(path_b.begin(), path_b.end(), total_a[v]);
            
            // it - path_b.begin() 是这个元素的位置（0-based index）
            // 这个位置表示有多少个前缀的b值和 <= total_a[v]
            // 这个数量等于最长有效前缀的节点数，减1就是边的数量（即路径长度）
            ans_arr[v] = (it - path_b.begin()) - 1;

            // 将子节点v压入栈，继续深入探索
            st.push(v);
        } else { // 如果u的所有子节点都已访问完毕 (这是DFS的“回溯”部分)
            st.pop(); // 将u出栈
            path_b.pop_back(); // 从路径记录中移除u的信息，恢复到其父节点的状态
        }
    }

    // 按要求输出结果
    for (int i = 2; i <= n; i++) {
        cout << ans_arr[i] << (i == n ? "" : " ");
    }
    cout << '\n';
}

int main() {
    // 加速输入输出，对付大数据的好习惯喵~
    ios::sync_with_stdio(false);
    cin.tie(0);

    int t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

复杂度分析喵~

时间复杂度: O(N log N) 的说每个节点在DFS过程中只会被访问一次。在访问每个节点 v 时，我们都会在 path_b 向量上执行一次二分查找。path_b 的大小等于当前节点的深度 depth(v)。在最坏的情况下（树是一条链），深度可以是 O(N)。所以，对于每个节点的操作耗时 O(log(depth(v)))。总的时间复杂度就是所有节点二分查找时间的总和，约为 O(N log N)。
空间复杂度: O(N) 的说我们需要 O(N) 的空间来存储树的邻接表 graph，以及 total_a, total_b, ans_arr 等数组。DFS过程中使用的栈 st 和路径向量 path_b 的最大深度也是 O(N)（在链状树的情况下）。所以总的空间复杂度是 O(N) 呐。

知识点与总结喵~

这道题真是一次愉快的冒险呢！让我们来总结一下学到了什么吧~

核心思想: DFS + 二分查找 是解决树上路径问题的强大组合拳！当问题涉及到从根出发的路径，并且路径上的某个属性（比如本题的 b 值前缀和）具有单调性时，一定要想想能不能用二分查找来优化哦。
DFS 技巧: 使用一个动态数组（vector）来维护当前DFS路径上的状态（push_back 进入，pop_back 回溯）是一个非常经典且实用的技巧。它能让我们在正确的上下文中进行计算。
迭代式DFS: 对于深度可能很大的树，用栈手动模拟的迭代式DFS比递归式DFS更安全，可以有效避免“栈溢出”（Stack Overflow）的悲剧。next_index 数组是实现这种迭代式DFS的关键，它帮助我们记住每个节点访问到了哪个孩子。
std::upper_bound: 这个函数是二分查找的好帮手！要牢记它返回的是第一个大于目标值的元素的迭代器。理解它的行为能让我们准确地计算出需要的结果。

总之，只要观察到题目中的单调性，再结合对树的遍历，问题就迎刃而解啦！希望这次的题解能帮到主人，继续加油，向着更高的目标前进吧，喵~ (≧∇≦)ﾉ

G. Path Prefixes - 题解 ​

比赛与标签 ​

题目大意喵~ ​

解题思路喵~ ​

代码实现喵~ ​

复杂度分析喵~ ​

知识点与总结喵~ ​