题目描述

难度分:$1500$

输入$T(\leq 10^4)$表示$T$组数据。所有数据的$n$之和$\leq 2 \times 10^5$。

每组数据输入$n(2 \leq n \leq 2 \times 10^5)$和长为$n$的数组$a(0 \leq a[i] \leq 10^9)$，表示一棵$n$个节点的树，节点$i$的点权为$a[i]$。

然后输入$p_2,p_3,…,p_n$，表示节点$2,3,…,n$的父节点。节点编号从$1$到 $n$，其中$1$是根节点。

你可以执行如下操作任意次：
选择点$v$，把$a[v]$加一，把子树$v$中的除了$v$以外的所有点的点权都减一。
操作后，所有点权都必须$\geq 0$。

输出根节点点权$a[1]$的最大值。

输入样例

3
4
0 1 0 2
1 1 3
2
3 0
1
5
2 5 3 9 6
3 1 5 2

输出样例

1
3
6

算法

树形DP

状态定义

$f[u]$表示以$u$为根的子树中的最小点权。

状态转移

这个转移比较简单，$u$的点权$a[u]$和其所有子树$v$中的最小点权$f[v]$比较就可以得到$f[u]$，状态转移方程为$f[u]=min(a[u],min_{v}f[v])$，其中$v$是$u$的子节点。

贪心

有了$f$数组就可以计算答案了，有一个比较明显的贪心思路。为了操作更多，从而使得加$1$操作转移到根节点$1$，最好的方式就是让点权尽可能均匀分配。对于某个节点$u$，我们先获得它所有子树中的最小点权$mn=min_{v}f[v]$，然后分为以下两种情况：

1. 如果$u=1$，那直接把$mn$这个权值减至$0$，这样$a[1]$可以增加$mn$就是答案。
2. 如果$a[u] \geq mn$，那$u$子树的最小点权就还是$mn$，上面的节点如果要进行操作，那操作次数会受限于$mn$。如果$a[u] \lt mn$，那我们就把$mn$匀上来，让子树$u$的最小点权变为$\lfloor \frac{a[u]+mn}{2} \rfloor$，其实就是在子树中增大$u$的点权$a[u]$，减小其他节点的点权，这样能提升子树$u$整体的最小点权，使得上面的节点可以操作更多次。

复杂度分析

时间复杂度

两次DFS遍历整棵树，时间复杂度为$O(n)$.

空间复杂度

树的邻接表空间消耗为$O(n)$；DP数组$f$是线性的，空间复杂度为$O(n)$；在最差情况下，DFS的深度为$O(n)$级别（树退化成链）。因此，整个算法的额外空间复杂度为$O(n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

const int N = 200010, INF = 0x3f3f3f3f;
int t, n, a[N], p[N];
long long f[N];
vector<int> graph[N];

void dfs1(int u, int fa) {
    f[u] = a[u];
    for(int v: graph[u]) {
        if(v == fa) continue;
        dfs1(v, u);
        f[u] = min(f[u], f[v]);
    }
}

void dfs2(int u, int fa) {
    LL min_val = INF;
    for(int v: graph[u]) {
        if(v == fa) continue;
        dfs2(v, u);
        min_val = min(min_val, f[v]);
    }
    if(u == 1) {
        f[u] = a[u] + min_val;
    }else {
        if(min_val != INF) {
            if(a[u] < min_val) {
                f[u] = (a[u] + min_val) / 2;
            }else {
                f[u] = min_val;
            }
        }
    }
}

int main() {
    scanf("%d", &t);
    for(int cases = 1; cases <= t; cases++) {
        scanf("%d", &n);
        for(int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
            graph[i].clear();
            f[i] = 2e9;
        }
        for(int i = 2; i <= n; i++) {
            scanf("%d", &p[i]);
            graph[p[i]].push_back(i);
        }
        dfs1(1, 0);
        dfs2(1, 0);
        printf("%lld\n", f[1]);
    }
    return 0;
}