来自 2023SDPT-Round1-Day4 课上 Qingyu 的讲解。
考虑对于一个点多次操作会发生什么？第一次操作会将周围的点的权值吸过来，自己对答案的贡献乘 \(-1\)，周围的点的贡献乘 \(+1\)，得到新的权值 \(a_x' = \pm a_x \mp \sum_{y \in son_x} a_y\)；再一次操作，我们可以将这个新的贡献取反。于是我们可以得到如果一个点被操作，那么他最后的贡献可以自由控制符号，答案求的是最大值，\(|a_i'|\) 的绝对值号可以拆开算贡献。
来点暴力 DP。很自然能够想到分成三种进行讨论：自己的值被父亲吸走，自己的值被儿子吸走，自己吸走别人的值。那么不妨设 \(f_{x,0/1/2,0/1}\) 记录，第一维是节点编号，第二维是三种情况讨论，第三维是当前节点是否吸走了父亲的值，DP 的值即为按这种方式转移能够得到的最大答案。接下来考虑如何转移：
- 首先我们钦定如果是 \(f_{x,0,0/1}\) 即被父亲吸走后，依旧可以操控这个状态来继续吸取儿子；如果是 \(f_{x,1,0/1}\) 即被某个儿子吸走后，依旧可以操控这个状态来吸取父亲和其他儿子；
- 能够注意到 \(f_{x,0,1}\) 是没有意义的，因为不可能自己的值被父亲吸走，又吸走了父亲的值。这一维恒为 \(0\)；
- 记 \(A_x\) 为 \(f_{son_x,0,0} \pm val_x,f_{son_x,1,0},f_{son_x,2,0}\) 中的最大值，\(B_x\) 为 \(f_{son_x,0,0} \pm val_x,f_{son_x,2,0}\)，\(C_x\) 为 \(f_{son_x,1,1},f_{son_x,2,1}\)，其中 \(f_{son_x,0,0} \pm val_x\) 并不是对两种运算去最值，而是对应第一段中那个式子的两种情况；
- 对于 \(f_{x,0,0}\) 即被父亲吸了，那么儿子对转移过来的值的贡献就是每个儿子的最优值，即 \(\sum A_{son_x}\)；
- 对于 \(f_{son_x,1,0/1}\) 即被儿子吸了的，我们在决策被哪一个儿子吸收的时候，贪心的看一下不加那个儿子的权值最优即可，去掉的儿子即为 \(A_{son_x} - C_{son_x}\) 最小的那个，将该值即为 \(D_i\)，儿子对转移过来的值的贡献即为 \(\sum A_{son_x} - D_i\)。吸了父亲的情况再加上对应情况的父亲的权值即可；
- 对于 \(f_{son_x,2,0/1}\) 即自己吸收的，儿子对转移过来的值的贡献即为 \(\sum B_{son_x}\)，最后还要对应的加或减去自身的权值。吸了父亲的情况再加上对应情况的父亲的权值即可；
- 对于每个点，分别记录一遍两种情况的 \(A_x,B_x,C_x\)，再加上对应计算方式（第一段中的式子）的本身节点的权值，看一看选取哪个最优；
- 最后的答案即为 \(\max{(f_{root,1,0},f_{root,2,0})}\)。
由此我们只需要遍历树一遍，记录和转移 DP 数组，细节还是很多的。时间复杂度为 \(\mathcal O(n)\)。
#include<bits/stdc++.h>
#define ld long double
#define ull unsigned long long
#define int long long
#define pb push_back
#define mp make_pair
using namespace std;
inline int read()
{
int s=0,w=1; char c=getchar();
while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
while(isdigit(c)) s=(s<<1)+(s<<3)+(c^48),c=getchar();
return s*w;
}
inline void write(int x,char ch)
{
if(x<0) x=-x,putchar('-');
static char stk[25]; int top=0;
do {stk[top++]=x%10+'0',x/=10;} while(x);
while(top) putchar(stk[--top]);
putchar(ch);
return;
}
namespace MyTool
{
static const int Mod=1e9+7;
template<typename T> inline void Swp(T &a,T &b) {T t=a;a=b;b=t;}
inline int Max(int a,int b) {return (b&((a-b)>>63))|(a&(~(a-b)>>63));}
inline int Min(int a,int b) {return (a&((a-b)>>63))|(a&(~(a-b)>>63));}
template<typename T> inline void cmax(T &a,T b) {a=a>b?a:b;}
template<typename T> inline void cmin(T &a,T b) {a=a<b?a:b;}
inline int Abs(int a) {return (a^(a>>63))-(a>>63);}
inline void Madd(int &a,int b) {a=a+b>Mod?a+b-Mod:a+b;}
inline void Mdel(int &a,int b) {a=a-b<0?a-b+Mod:a-b;}
inline void Mmul(int &a,int b) {a=1ll*a*b%Mod;}
inline void Mmod(int &a) {a=(a%Mod+Mod)%Mod;}
inline int Cadd(int a,int b) {return a+b>=Mod?a+b-Mod:a+b;}
inline int Cdel(int a,int b) {return a-b<0?a-b+Mod:a-b;}
inline int Cmul(int a,int b) {return a*b%Mod;}
inline int Cmod(int a) {return (a%Mod+Mod)%Mod;}
inline int gcd(int a,int b) {return b?gcd(b,a%b):a;}
inline int qpow(int a,int b) {int res=1; while(b) {if(b&1) Mmul(res,a); Mmul(a,a); b>>=1;} return res;}
inline int qmul(int a,int b) {int res=0; while(b) {if(b&1) Madd(res,a); Madd(a,a); b>>=1;} return res;}
template<typename T> inline T pow(T x) {return x*x;}
}
using namespace MyTool;
inline void file()
{
freopen(".in","r",stdin);
freopen(".out","w",stdout);
return;
}
bool Mbe;
namespace LgxTpre
{
static const int MAX=500000;
static const int inf=2147483647;
static const int INF=4557430888798830399;
static const int mod=998244353;
static const int bas=131;
int n,val[MAX],fa[MAX];
vector<int> G[MAX];
int f[MAX][3][2];
void dfs(int now)
{
int zsum1=0,zsum2=0,zmix=INF;
int fsum1=0,fsum2=0,fmix=INF;
for(auto to:G[now])
{
dfs(to);
zsum1+=max({f[to][0][0]+val[to],f[to][1][0],f[to][2][0]});
zsum2+=max({f[to][0][0]+val[to],f[to][1][0]});
cmin(zmix,max({f[to][0][0]+val[to],f[to][1][0],f[to][2][0]})-max({f[to][1][1],f[to][2][1]}));
fsum1+=max({f[to][0][0]-val[to],f[to][1][0],f[to][2][0]});
fsum2+=max({f[to][0][0]-val[to],f[to][1][0]});
cmin(fmix,max({f[to][0][0]-val[to],f[to][1][0],f[to][2][0]})-max({f[to][1][1],f[to][2][1]}));
}
f[now][0][0]=max(zsum1,fsum1);
f[now][1][0]=max(zsum1-zmix,fsum1-fmix);
f[now][1][1]=max(zsum1-zmix+val[fa[now]],fsum1-fmix-val[fa[now]]);
f[now][2][0]=max(zsum2-val[now],fsum2+val[now]);
f[now][2][1]=max(zsum2-val[now]+val[fa[now]],fsum2+val[now]-val[fa[now]]);
return;
}
inline void mian()
{
n=read();
for(int i=1;i<=n;++i) val[i]=read();
for(int i=2;i<=n;++i) fa[i]=read(),G[fa[i]].pb(i);
dfs(1);
write(max({f[1][1][0],f[1][2][0]}),'\n');
return;
}
}
bool Med;
signed main()
{
// file();
fprintf(stderr,"%.3lf MB\n",(&Med-&Mbe)/1048576.0);
LgxTpre::mian();
cerr<<1e3*clock()/CLOCKS_PER_SEC<<" ms\n";
return (0-0);
}