题解：【CTS2022】 独立集问题

题目链接

来自 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);
}