一家公司里有 n
个员工，他们的编号分别是 1
到 n
，其中 1
号员工是公司 CEO，CEO 在公司里没有上司。除了 CEO 外，每个人都有一个直接上司。今天公司要办一个舞会，为了大家玩得尽兴，如果某个员工的直接上司来了，他/她就不想来了。i
号员工来参加舞会会为大家带来 ai
点快乐值。现在我们想要确定一组员工参加舞会的方案，使得快乐值总和最大。请求出快乐值总和最大是多少。
输入格式
第一行一个整数 n
。
接下来一行 n−1
个整数 f2,f3,…,fn
，其中 fi
(1≤fi<i)
表示 i
号员工的上司的编号。
接下来一行 n
个整数 a1,a2,…,an
表示每个员工参加舞会带来的快乐值。
输出格式
一行一个整数表示答案。
样例输入
5
1 2 3 1
1 8 10 8 2
样例输出
18
数据规模
对于所有数据，保证 2≤n≤105,1≤ai≤105
。
树形DP
注意输入的父节点值都小于i，则只需要保留一条边p->i
点击查看代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
vector<int> v[N];
ll dp[N][2];
int a[N];
void dfs(int p)
{
for(auto x:v[p])
{
dfs(x);
dp[p][0]+=max(dp[x][0],dp[x][1]);
dp[p][1]+=dp[x][0];
}
dp[p][1]+=a[p];
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int n;
cin>>n;
for(int i=2;i<=n;++i)
{
int fi;
cin>>fi;
v[fi].push_back(i);
}
for(int i=1;i<=n;++i) cin>>a[i];
dfs(1);
cout<<max(dp[1][0],dp[1][1])<<'\n';
return 0;
}