P1612 题解

oddy · 2022-10-08 21:59:45 · 题解

第一次给扶苏出的题写题解，开心~

题意简述

题面已经非常简洁了，跳过。

解题思路

我们发现，对于每一个节点，它对应的链的另一个端点一定在它到根的简单路径——一条链上。

记 s_i 为从根到节点 i 的权值和，因为所有权值均为正整数，所以在以根为端点的一条链上，s_i 必然递增，则考虑二分。

具体地讲，DFS 遍历这棵树，维护一个与此时的递归调用栈同步的栈，对于每个节点，算出它的 s_i，然后在这个栈上二分。

二分的数值是多少呢？记另一个节点为 v，则题目要求，权值和，即 s_u-s_v\leqslant c_u，故 s_v\geqslant s_u-c_u，则要二分的值为 s_u-c_u。

代码

#include <cstdio>
#include <vector>
#include <algorithm>

int n, p, ans[100005], q[100005], tail; // q 是我们维护的栈
long long w[100005], c[100005], s[100005];
std::vector<int> e[100005];

bool cmp(const int &x, const long long &y) {
    return s[x] < y;
}

void dfs(int x) {
    q[tail++] = x;
    ans[x] = q + tail - std::lower_bound(q, q+tail, s[x] - c[x], cmp) - 1; // 二分找到位置，算出距离

    for(const int &p : e[x]) s[p] = s[x] + w[p], dfs(p); // 算出子节点的前缀和，接着往下递归
    tail--;
}

int main() {
    scanf("%d", &n);
    e->emplace_back(1); // 为了方便操作，设 0 为 1 的父节点
    for(int i = 2; i <= n; i++)
        scanf("%d", &p), e[p].emplace_back(i);

    for(int i = 1; i <= n; i++) scanf("%lld", w+i);
    for(int i = 1; i <= n; i++) scanf("%lld", c+i);

    dfs(0);

    for(int i = 1; i <= n; i++) printf("%d ", ans[i]);

    return 0;
}