【题解】P7925 「EVOI-RD2」童年
题目传送门。
插嘴：感觉没有蓝的难度。
解题思路：
-
了解题意后考虑模拟摘苹果的过程，即贪心。
-
因为我们可以先摘苹果后处理鸟巢，而且摘完一个子树上所有苹果后手中的苹果必定是最大值，所以摘完苹果后仍旧不能通过鸟巢的话，其他情况也不行。又因为每个子树上苹果数固定，所以可以考虑在以鸟巢为根的子树上，先摘子树上苹果多的那个子树。
-
先预处理出每个子树上点权之和，然后正数按照点权，负数按子树和排序，这样就满足贪心了。
-
模拟摘苹果的过程，进入每个子树，若摘出来后的苹果还没有原先的多，则不去摘，总苹果数不变，反则变为摘后的苹果数。
-
然后特判一下特殊情况，比如进不去、不如不摘、链等情况，便可通过本题。
AC 代码
#include<bits/stdc++.h>
using namespace std;
const int M(6001);
#define int long long
struct node{int to,next;};
node t[M<<1];int tot,head[M];
int n,siz[M],fa[M],val[M];
struct poss{int id,val,siz;};
poss dp[M];int cnt,s,flag;
vector<poss> son[M];
inline bool cmp(poss x,poss y){
if(x.val<0&&y.val<0) return x.siz>y.siz;
return x.val>y.val;
}
inline void add(int u,int v){
t[++tot]={v,head[u]};head[u]=tot;
t[++tot]={u,head[v]};head[v]=tot;
}
inline void _dfs(int x){
siz[x]=val[x];
for(int y,i(head[x]);i;i=t[i].next){
if((y=t[i].to)==fa[x]) continue;
fa[y]=x;_dfs(y);siz[x]+=siz[y];
dp[++cnt]={y,val[y],siz[y]};
son[x].push_back(dp[cnt]);
}
}
inline void dfs(int x,int &b){
if(son[x].size()<1) return ;
int top(b);
sort(son[x].begin(),son[x].end(),cmp);
for(int i(0);i<son[x].size();++i){
if(val[son[x][i].id]<0&&-val[son[x][i].id]<=b){
b+=val[son[x][i].id];
dfs(son[x][i].id,b);
}
else if(val[son[x][i].id]>=0){
b+=val[son[x][i].id];
dfs(son[x][i].id,b);
}
if(b<top) b=top;
else top=b;
}
}
signed main(){
cin>>n>>s;
for(int i(2),u;i<=n;++i){
cin>>u;add(u,i);
if(u!=i-1) flag=1;
}
for(int i(1);i<=n;++i)
cin>>val[i];
if(!flag){
int ans(s),sum(s);
for(int i(1);i<=n;++i){
sum+=val[i];
if(sum<0) break;
ans=max(sum,ans);
}
cout<<ans;return 0;
}
_dfs(1);
if(s>-val[1]&&val[1]<0) s+=val[1];
else if(val[1]>0) s+=val[1];
else {
cout<<s;return 0;
}
dfs(1,s);
cout<<s;return 0;
}