Burnling's Blog
0%

CF1997D Maximize the Root

发表于 更新于 分类于 ，

题意简述

给定一个有根树，共有 $n$ 个顶点，顶点编号从 $1$ 到 $n$，根为顶点 $1$。在第 $i$ 个顶点写有一个值 $a_i$。

你可以进行以下操作任意次（可能为零次）：

  1. 选择一个至少有一个子节点的顶点 $v$；
  2. 将顶点 $v$ 的值 $a_v$ 增加 1；
  3. 将顶点 $v$ 子树中的所有顶点（除了 $v$ 本身）的值 $a_u$ 减少 1。

但操作后每个顶点的值必须是非负数。

你的任务是计算通过上述操作后根节点上能写的最大值。

思路分析

容易想到，对于以节点 $v$ 为根的子树，顶点 $v$ 最多能进行 $\min\limits_{i \in D} a_i$ 次操作，其中集合 $D$ 为以节点 $v$ 为根的子树中的所有节点形成的集合。

那么如果要让根节点上的权值最大，我们需要使子树中的最小值最大。

设 $\text{dp}_i$ 表示以 $i$ 为根的子树中，所有节点权值的最小值。

对于某一个节点 $u$，有两种情况：

  1. $au \leq \min\limits{u\to v} \text{dp}_v$，即以节点 $u$ 为根的子树中，节点 $u$ 的权值最小。

    那么为了尽可能地使 $\text{dp}{u}$ 增大，可以进行若干次操作，使 $a{u} \ge \min\limits{u\to v} \text{dp}{v}$。

    我们没有必要一次次地模拟。

    由于最终结果为满足 $a{u} \ge \min\limits{u\to v} \text{dp}{v}$ 的最小的 $a{u}$，所以 $\text{dp}{u} \gets \left\lfloor\dfrac{a{u} + \min\limits{u\to v} \text{dp}{v}}{2}\right\rfloor$。

  2. $au \gt \min\limits{u\to v} \text{dp}_v$，此时 $\text{dp}_u = a_u$。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<bits/stdc++.h>
using namespace std;

const int maxN = 3e5 + 10;
int A[maxN];

vector<int> G[maxN];
int fa[maxN];
int mad[maxN];
int dp[maxN];

void dfs(int p){
    if(!G[p].size()) return;
    int mi = 2e9;
    for(auto v : G[p]){
        dfs(v);
        mi = min(mi,dp[v]);
    }
    if(p == 1){
        dp[p] += mi;
        return;
    }
    if(A[p] < mi) dp[p] = ((1ll * mi + A[p]) >> 1);
    else dp[p] = mi;

}
inline void solve(){
    int N;
    scanf("%d",&N);
    
    for(int i = 1;i<=N;i++) scanf("%d",&A[i]);
    for(int i = 1;i<=N;i++){
        G[i].clear();
        dp[i] = A[i];
    } 
    for(int i = 2;i<=N;i++){
        int t;
        scanf("%d",&t);
        G[t].push_back(i);
        fa[i] = t;
    }
    dfs(1);
    printf("%d\n",dp[1]);
}

int main(){
    int T;
    scanf("%d",&T);
    while(T--) solve();
    return 0;
}