专栏文章

题解：P8294 [省选联考 2022] 最大权独立集问题

居居然有个高手
P8294题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mipx3o4b
此快照首次捕获于
2025/12/03 19:22
3 个月前
此快照最后确认于
2025/12/03 19:22
3 个月前
查看原文
超级分讨题吗，哈哈那无敌了。
这种题可以先想一下怎么做多项式复杂度。考虑一个点的度数至多为 33，因此我们可以分类讨论一下有关其交换的顺序。我们发现在交换了 xx 与 faxfa_x 之间的边后 xx 子树内为独立问题，可以想到记录子树型状态。
那么我们要记录什么样的状态呢？显然我们关心 xx 与 faxfa_x 交换时的值，同时还有 xx 的儿子的交换状态。同时我们又发现，若钦定交换时 dx=i,dfax=jd_x = i,d_{fa_x}=j，则在二者交换前，对于 xx 子树内，我们只关心让 xx 留下的值为 ii 时的最小代价；交换后我们只关心 xx 目前带的值为 jj 时的最小代价。
因此我们可以记录 fx,i,0/1/2f_{x,i,0/1/2} 与 gx,i,0/1/2g_{x,i,0/1/2} 表示 xx 初始时带的权值为 aia_i，进行了 0/1/20/1/2 状态的交换操作后子树内的最小代价；gx,i,0/1/2g_{x,i,0/1/2} 表示 xx 进行了 0/1/20/1/2 状态的操作后，最终保留权值为 aia_i 时子树内的最小代价。（00 表示只换左子树，11 表示只换右子树，22 表示都换）
显然，fx,i,opf_{x,i,op} 状态有效当且仅当 i=xi=x 或 ii 在 xx 子树外，gx,i,opg_{x,i,op} 状态有效当且仅当 ii 在 xx 子树内。
开始分讨转移了。对于 fx,i,0f_{x,i,0}，我们枚举此时左子树 lsls 的交换情况：
未交换：fx,i,0=als+ai+fls,i,2f_{x,i,0}=a_{ls}+a_i+f_{ls,i,2}。
交换一边（记作 opop）：fx,i,0=ai+min⁡j{gls,j,op+aj+fls,i,1−op}f_{x,i,0}=a_i+\underset j\min\{g_{ls,j,op} + a_j + f_{ls,i,1-op}\}。
交换两边：fx,i,0=ai+min⁡j{gls,j,2+aj}f_{x,i,0}=a_i + \underset j \min\{g_{ls,j,2}+a_j\}。
容易发现上式中 i,ji,j 不同时出现，因此预处理 gls,j,op+ajg_{ls,j,op}+a_j 的最小值即可。
对于 gx,i,0g_{x,i,0}，我们同样枚举交换情况：
未交换：此时 i=lsi=ls，gx,i,0=als+ax+fls,x,2g_{x,i,0}=a_{ls}+a_x+f_{ls,x,2}。
交换一边：gx,i,0=ai+ax+gls,i,op+fls,x,1−opg_{x,i,0}=a_i + a_x + g_{ls,i,op} + f_{ls,x,1-op}。
交换两边：gx,i,0=ai+ax+gls,i,2g_{x,i,0} = a_i+a_x+g_{ls,i,2}。
fx,i,1f_{x,i,1}，gx,i,1g_{x,i,1} 均为对偶情况，不多加赘述。
而对于 fx,i,2f_{x,i,2} 我们分讨先交换左子树还是右子树，则对于另一侧子树而言是 fx,i,opf_{x,i,op} 的情况，我们可以仿照上文分讨，并进行适当预处理即可解决。
对于 gx,i,2g_{x,i,2}，我们应当考虑其来自哪颗子树，那么自然钦定了左右子树的先后顺序；若其恰好为 lsls 或 rsrs 时则钦定了 ii 点的交换顺序，进行上文中大小为 44 的分讨即可（有两种对偶情况，因此文中只呈现 33 种，代码中可以得到完整体现）；否则对两侧子树进行大小为 1212 的分类讨论。仿照上文稍加讨论即可得到，具体细节可参考代码。
在一切计算中，我们容易发现虽然会出现临时变量 jj，但其总不与 ii 相关，因此我们可以预处理多种 jj 相关的计算式最小值，枚举 ii 计算时简单调用即可保证复杂度。
最终答案即为 f1,1,2f_{1,1,2}，本题在 O(n2)O(n^2) 的时空复杂度内得到解决。
贴一份代码：
CPP
#include <bits/stdc++.h>
using namespace std;
const int N=5005;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return x*f;
}
long long f[N][N][3],g[N][N][3],mn1[N][3],mn2[N][3],mn3[N][3][3],mn4[N][3],a[N];
int n,dfn[N],ed[N],cnt;
vector<int>e[N];
inline void pre(int x){
	dfn[x]=++cnt;
	for(auto y : e[x])pre(y);
	ed[x]=cnt;
}
inline void dfs(int x){
	for(auto y : e[x])dfs(y);
	if(e[x].empty()){
		for(int i = 1;i<=n;i++)f[x][i][0]=f[x][i][1]=f[x][i][2]=0;
		g[x][x][0]=g[x][x][1]=g[x][x][2]=0;
	}
	if(e[x].size()>=1){
		int ls = e[x][0];
		for(int i = 1;i<=n;i++){
			if(dfn[i]<dfn[ls]||dfn[i]>ed[ls]){
				f[x][i][0]=a[i]+a[ls]+f[ls][i][2];
				f[x][i][0]=min(f[x][i][0],a[i] + min(mn1[ls][0] + f[ls][i][1],min(mn1[ls][1] + f[ls][i][0],mn1[ls][2])));
			}
			else if(i==ls)g[x][ls][0]=a[x]+a[ls]+f[ls][x][2];
			else{
				g[x][i][0]=a[x]+a[i]+min(g[ls][i][0] + f[ls][x][1],min(g[ls][i][1] + f[ls][x][0],g[ls][i][2]));
			}
		}
	}
	if(e[x].size()==1){
		int ls = e[x][0];
		for(int i = 1;i<=n;i++){
			if(dfn[i]<dfn[ls]||dfn[i]>ed[ls])f[x][i][2]=f[x][i][0],f[x][i][1]=0;
			else g[x][i][2]=g[x][i][0],g[x][i][1]=1e18;
		}
	}
	if(e[x].size()==2){
		int ls=e[x][0],rs=e[x][1];
		for(int i = 1;i<=n;i++){
			if(dfn[i]<dfn[rs]||dfn[i]>ed[rs]){
				f[x][i][1]=a[i] + a[rs] + f[rs][i][2];
				f[x][i][1]=min(a[i] + min(mn1[rs][0] + f[rs][i][1],min(mn1[rs][1] + f[rs][i][0],mn1[rs][2])),f[x][i][1]);
			}
			else if(i==rs)g[x][rs][1]=a[x]+a[rs]+f[rs][x][2];
			else{
				g[x][i][1]=a[x]+a[i]+min(g[rs][i][0] + f[rs][x][1],min(g[rs][i][1] + f[rs][x][0],g[rs][i][2]));
			}
		}
		for(int j = 1;j<=n;j++){
			if(dfn[ls]<=dfn[j]&&dfn[j]<=ed[ls]){
				for(int k = 0;k<3;k++){
					mn2[ls][k]=min(mn2[ls][k],g[ls][j][k]+a[j]+f[x][j][1]);
					mn4[ls][k]=min(mn4[ls][k],g[ls][j][k]+a[j]*2);
					for(int o = 0;o<3;o++)mn3[ls][k][o]=min(mn3[ls][k][o],g[ls][j][k] + 2*a[j] + f[rs][j][o]);
				}
			}
			else if(dfn[rs]<=dfn[j]&&dfn[j]<=ed[rs]){
				for(int k = 0;k<3;k++){
					mn2[rs][k]=min(mn2[rs][k],g[rs][j][k]+a[j]+f[x][j][0]);
					mn4[rs][k]=min(mn4[rs][k],g[rs][j][k]+a[j]*2);
					for(int o = 0;o<3;o++)mn3[rs][k][o]=min(mn3[rs][k][o],g[rs][j][k] + 2*a[j] + f[ls][j][o]);
				}
			}
		}
		for(int i = 1;i<=n;i++){
			if(dfn[i]<=dfn[x]||dfn[i]>ed[x]){
				f[x][i][2] = a[i] + f[ls][i][2] + a[ls] + f[x][ls][1];
				f[x][i][2]=min(f[x][i][2],min(a[i] + mn2[ls][0] + f[ls][i][1],a[i] + mn2[ls][1] + f[ls][i][0]));
				f[x][i][2]=min(f[x][i][2],a[i] + mn2[ls][2]);
				f[x][i][2] = min(f[x][i][2],a[i] + f[rs][i][2] + a[rs] + f[x][rs][0]);
				f[x][i][2]=min(f[x][i][2],min(a[i] + mn2[rs][0] + f[rs][i][1],a[i] + mn2[rs][1] + f[rs][i][0]));
				f[x][i][2]=min(f[x][i][2],a[i]+mn2[rs][2]);
			}
			else if(dfn[ls]<=dfn[i]&&dfn[i]<=ed[ls]){
				if(i==ls){
					g[x][i][2]=a[x] + f[rs][x][2] + a[rs] + f[ls][rs][2] + a[rs] + a[i];
					g[x][i][2]=min(g[x][i][2],min(a[x] + mn3[rs][0][2] + f[rs][x][1] + a[i],a[x] + mn3[rs][1][2] + f[rs][x][0] + a[i]));
					g[x][i][2]=min(g[x][i][2],mn3[rs][2][2] + a[x] + a[i]);
				}
				else{
					g[x][i][2]=a[x]+a[i]+a[rs]*2+f[rs][x][2]+min(g[ls][i][2],min(g[ls][i][0]+f[ls][rs][1],g[ls][i][1]+f[ls][rs][0]));
					g[x][i][2]=min(g[x][i][2],a[x]+a[i]+g[ls][i][2]+min(min(f[rs][x][1]+mn4[rs][0],f[rs][x][0]+mn4[rs][1]),mn4[rs][2]));
					g[x][i][2]=min(g[x][i][2],a[x]+a[i]+min(min(mn3[rs][2][0]+g[ls][i][1],mn3[rs][2][1]+g[ls][i][0]),mn4[rs][2]+g[ls][i][2]));
					for(int o = 0;o<2;o++)for(int k = 0;k<2;k++)g[x][i][2]=min(g[x][i][2],a[x]+a[i]+f[rs][x][o^1]+mn3[rs][o][k^1]+g[ls][i][k]);
				}
			}
			else{
				if(i==rs){
					g[x][i][2]=a[x] + f[ls][x][2] + a[ls] + f[rs][ls][2] + a[ls] + a[i];
					g[x][i][2]=min(g[x][i][2],min(a[x] + mn3[ls][0][2] + f[ls][x][1] + a[i],a[x] + mn3[ls][1][2] + f[ls][x][0] + a[i]));
					g[x][i][2]=min(g[x][i][2],mn3[ls][2][2] + a[x] + a[i]);
				}
				else{
					g[x][i][2]=a[x]+a[i]+a[ls]*2+f[ls][x][2]+min(g[rs][i][2],min(g[rs][i][0]+f[rs][ls][1],g[rs][i][1]+f[rs][ls][0]));
					g[x][i][2]=min(g[x][i][2],a[x]+a[i]+g[rs][i][2]+min(min(f[ls][x][1]+mn4[ls][0],f[ls][x][0]+mn4[ls][1]),mn4[ls][2]));
					g[x][i][2]=min(g[x][i][2],a[x]+a[i]+min(min(mn3[ls][2][0]+g[rs][i][1],mn3[ls][2][1]+g[rs][i][0]),mn4[ls][2]+g[rs][i][2]));
					for(int o = 0;o<2;o++)for(int k = 0;k<2;k++)g[x][i][2]=min(g[x][i][2],a[x]+a[i]+f[ls][x][o^1]+mn3[ls][o][k^1]+g[rs][i][k]);
				}
			}
		}
	}
	for(int j = 1;j<=n;j++){
		if(dfn[x]<=dfn[j]&&dfn[j]<=ed[x]){
			for(int o = 0;o<3;o++)mn1[x][o]=min(mn1[x][o],g[x][j][o]+a[j]);
		}
	}
}
int main(){
	n=read();
	for(int i = 1;i<=n;i++)a[i]=read();
	for(int i = 2;i<=n;i++)e[read()].push_back(i);
	pre(1);
	memset(f,0x3f,sizeof f);memset(g,0x3f,sizeof g);
	memset(mn1,0x3f,sizeof mn1);memset(mn2,0x3f,sizeof mn2);memset(mn3,0x3f,sizeof mn3);memset(mn4,0x3f,sizeof mn4);
	dfs(1);
	cout<<f[1][1][2];
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...