[CTS2022] 独立集问题
考虑一个点被操作多次会发生什么
具体而言 设点\(x\)为操作点 \(u\)为满足\((x,u)\in E\) 的点
那么若对点\(x\)操作多次 其贡献为:\(val_x-\sum_u val_u\)或者\(-val_x+\sum_u val_u\) 这是一个简单的观察
发现此结构具有子结构性 那么不妨试着考虑\(dp\)
定义 \(dp_i,_{0/1/2},_{0/1}\) 其表示为：
- 第一维为处于何点
- 第二维的0/1/2 分别表示：
- 0：此点被父亲吸附
- 1：此点被儿子吸附
- 2：此点自我吸附其他点
- 第三维的0/1 表示为现在\(i\)这棵子树是否有过吸附父亲的行为 0代表没有 1代表有
- 其值代表的便是\(i\)这棵子树当所有点被缩为1个点时其值大小 位置不一定为\(i\)
第二维的"此点状态"均是指：在此点第一次做出操作/被操作时所属于状态
而第三维所指吸附父亲也是指 当父亲上的数仍是最初时的值时是否因\(x\)这个点的操作而被吸下去
那么就可以考虑转移了 值得一提的是 \(dp_x,_0,_1\)显然是不合法的 因为其矛盾
- \(dp_x,_0,_0\): 因为其第一次被父亲吸附 那么所属于\(x\)点的值就变为0 而其儿子\(son_x\)的子树中唯一有值的点便可以通过若干次操作到达\(son_x\)这个位置 转移便是：
- \(dp_x,_0,_0=\sum_{son_x}max(dp_{son_x},_0,_0\pm val_{son_x},dp_{son_x},_1,_0,dp_{son_x},_2,_0)\) \(\pm\) 便是来自于开头的观察
- \(dp_x,_1,_{0/1}\):此点被儿子吸附 为方便起见 我们定义\(A_x\)为\(\sum_{x}max(dp_{x},_0,_0\pm val_{x},dp_{x},_1,_0,dp_{x},_2,_0)\) 那么其转移应该是：
- \(dp_x,_1,_{0/1}=\sum A_{son_x}-C_y\) 其中\(y\)为某一个儿子 而\(C\)的取值为\(min(A_y-max(dp_x,_1,_1,dp_x,_2,_1))\) 含义便是将\(x\)纳入某一个儿子中 这是0的计算方式 1的话加或减去父亲的权值即可 加减取决于儿子的正负
- \(dp_x,_2,_{0/1}\) 此点自我吸附 那么其儿子的第二维也不应该有2状态 显然重叠 且儿子的第三维也不应该有1 于是可以轻松得到转移
- \(dp_x,_2,_{0/1}=\sum_{son_x}max(dp_{son_x},_0,_0\pm val_{son_x},dp_{son_x},_1,_0)\) 同样的 这是0的计算方式 对于1的计算方式仍是加或减去父亲 加减仍取决于儿子的正负
进行树上\(dp\) 每次记录两种情况的值 最后求最大值 答案即为\(max(dp_{root},_1,_0,dp_{root},_2,_0)\)
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=1e6+10;
const int INF=0x3f3f3f3f;
int n,d[maxn];
vector<int>g[maxn];
int dp[maxn][3][2],fa[maxn];
void dfs(int x){
int lA=0,lB=0,lC=INF;
int rA=0,rB=0,rC=INF;
for(auto k:g[x]){
fa[k]=x;
dfs(k);
lA=lA+max({dp[k][0][0]+d[k],dp[k][1][0],dp[k][2][0]});
lB=lB+max(dp[k][0][0]+d[k],dp[k][1][0]);
lC=min(lC,max({dp[k][0][0]+d[k],dp[k][1][0],dp[k][2][0]})-max(dp[k][1][1],dp[k][2][1]));
rA=rA+max({dp[k][0][0]-d[k],dp[k][1][0],dp[k][2][0]});
rB=rB+max(dp[k][0][0]-d[k],dp[k][1][0]);
rC=min(rC,max({dp[k][0][0]-d[k],dp[k][1][0],dp[k][2][0]})-max(dp[k][1][1],dp[k][2][1]));
}
dp[x][0][0]=max(lA,rA);
dp[x][1][0]=max(lA-lC,rA-rC);
dp[x][1][1]=max(lA-lC+d[fa[x]],rA-rC-d[fa[x]]);
dp[x][2][0]=max(lB-d[x],rB+d[x]);
dp[x][2][1]=max(lB-d[x]+d[fa[x]],rB+d[x]-d[fa[x]]);
}
signed main(){
std::ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++)cin>>d[i];
for(int i=2;i<=n;i++){
int x;cin>>x;
g[x].push_back(i);
}
dfs(1);
cout<<max(dp[1][1][0],dp[1][2][0]);
return 0;
}