自动搬运

查看原文

来自洛谷，原作者为

	oddy **

搬运于2025-08-24 21:27:05，当前版本为作者最后更新于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;
}