题解：CF1997D Maximize the Root

· · 题解

考虑类似贪心的做法。

对于每一个节点，若要使其节点能达到的值最大，则其子树中的节点中的最小值也一定要尽可能大。

定义 dis_i 为节点 i 的子树中所可能达到的最大的最小值。

假设 u 是 v 的子节点，接下来分类讨论：

如果 a_v\ge dis_u，那没什么好说的，dis_v 显然等于 dis_u（无法将父节点的值“传”给子节点）。

如果 a_v<dis_u，则 dis_v=\lfloor\dfrac{a_v+dis_u}{2}\rfloor（可以将子节点的值“传”给父节点，下取整的原因是求的是最小值）。

为什么这里不是将子树的权值全部加起来求平均值？因为父节点增加 1，所有其他的节点全部都要减 1，即只有最小值和原有的权值 a_v 决定了 dis_v 的值。

如果一个节点有多个子节点，显然取在多个算得结果中取最小值即可。

由于我们知道对于任意一个叶子节点 leaf，dis_{leaf}=a_{leaf}，那么根据上述操作我们可以得出整棵树的 dis 值。

问题来了，就算知道了 dis 数组怎么求题目要求的根节点最大值？

答案十分显然，将根节点权值和剩余节点中的最小值相加即可。

至于如何进行对树的遍历，方法一抓一大把，本人用的是拓扑排序，正确性无误即可。

此处提醒：注意多测清空以及清空方式，本人赛时查了半个小时错愣是没看出来。

上代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int dis[1000005];
int p[1000005];
int a[1000005];
int in[1000005];
struct node{
    int v,w,next;
}edge[1000005];
int num;
int head[1000005];
void add(int u,int v,int w){
    edge[++num].next=head[u];
    head[u]=num;
    edge[num].w=w;
    edge[num].v=v;
}
queue<int>q;
void tupo(){
    while(!q.empty()){
        int t=q.front();
        q.pop();
        if(t==1)continue;
        for(int i=head[t];i;i=edge[i].next){
            int v=edge[i].v;
            if(dis[t]>=a[v]){
                if(v==1){
                    dis[v]=min(dis[v],dis[t]);
                }
                else
                dis[v]=min(dis[v],(dis[t]+a[v])/2);
            }
            else{
                if(v==1){
                    dis[v]=min(dis[v],dis[t]);
                }
                else
                dis[v]=min(dis[v],min(dis[t],a[v]));
            }
            in[v]--;
            if(!in[v])q.push(v);
        }
    }
}
signed main(){
    int t;
    cin>>t;
    while(t--){
        while(!q.empty())q.pop();
        num=0;
        int n;
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>a[i];
            head[i]=0;
        }
        for(int i=1;i<=n;i++){
            in[i]=0;
        }
        for(int i=1;i<=n;i++){
            dis[i]=0x3f3f3f3f3f3f3f3f;
        }
        for(int i=2;i<=n;i++){
            int p;
            cin>>p;
            add(i,p,0);
            in[p]++;
        }
        for(int i=2;i<=n;i++){
            if(in[i]==0){
                q.push(i);
                dis[i]=a[i];
            }
        }
        tupo();
        cout<<dis[1]+a[1]<<endl;
    }
    return 0;
}