题解 | #牛牛的考试#

思路：

当几门课程没有关系的时候采用双开肯定会节约时间；我们可以考虑树，把1当作根来推。开两个数组，一个f[x]来存第x门课的时候花的最少时间；g[x]来存第x门课他的字树的总时间。每次x会有f[x]=max(f[i]),(其中i为x的子树），然后f[x]=a[x]+max(f[x],(g[x]-2f[x]+1)/2+f[x]),这是因为会有只有一个子树的情况，(g[x]-2f[x]+1)/2+f[x]）这部分是双开最少用时间，加1是因为整除的原因。

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
ll n,a[1000010],f[1000010],g[1000010];//f[x]来存第x门课的时候花的最少时间；g[x]来存第x门课他的字树的总时间
vector<ll>v[100010]; //v[x]用来存第x门课要在哪些课后面
void fun(ll x)
{
    for(auto i:v[x])
    {
        fun(i);
        f[x]=max(f[x],f[i]);//找最大的子树
        g[x]+=g[i];//子树和
    }
    f[x]=a[x]+max(f[x],(g[x]-2*f[x]+1)/2+f[x]);//学完第x门课的时间
    g[x]+=a[x];
}
int main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
    }
    for(int i=2;i<=n;i++)
    {
        ll k;scanf("%lld",&k);
        v[k].push_back(i);
    }
    fun(1);
    cout<<f[1];
    return 0;
}