树上可修改式背包
题目描述
给出一棵 n n n 个点以 1 1 1 为根的有根树，第 i i i 个点的父亲为 f i f_i fi ，每个点上有点权 a i a_i ai 。
你需要维护 m m m 次操作，操作分为两种：
-
格式为 1 x y 1\ x\ y 1 x y ，表示令 a x ⟵ y a_x\longleftarrow y ax⟵y。
-
格式为 2 x y 2\ x\ y 2 x y ，查询在点 x x x 的邻居中选出一个集合 S S S ，满足 ∑ i ∈ S a i = y \displaystyle\sum_{i\in S}a_i=y i∈S∑ai=y 的方案数对 998244353 998244353 998244353 取余的结果。
对于 100 % 100\% 100% 的数据， 1 ≤ n , q , a i , y ≤ 4 × 1 0 3 1\le n,q,a_i,y\le4\times10^3 1≤n,q,ai,y≤4×103， 1 ≤ x ≤ n 1\le x\le n 1≤x≤n 。
输入格式
第一行两个整数 n , q n,q n,q ，表示点数和操作次数。
第二行 n − 1 n-1 n−1 个整数，第 i i i 个为 f i f_i fi 。
第三行 n n n 个整数，第 i i i 个为 a i a_i ai 。
接下来 q q q 行描述了 q q q 次操作。
输出格式
对于操作 2 2 2 每行一个整数。
样例输入 1 1 1
4 3
1 1 1
1 2 2 2
2 1 6
1 2 3
2 1 5
样例输出 1 1 1
1
2
首先有个朴素的思路：对于每次询问，求一个背包。
但毫无疑问的是，会超时。
与普通的背包不同的是，这题对于每个点是可以修改的，我们考虑怎么快速完成这个修改。
令 d p i , j dp_{i,j} dpi,j 表示点 i i i 的所有儿子中部分的和为 j j j 的方案数，可以先将 d p f a i , j dp_{fa_i,j} dpfai,j 中除去 a i a_i ai ，然后将 a i a_i ai 改为 y y y ，再将 a i a_i ai 添回 d p f a i , j dp_{fa_i,j} dpfai,j 中。注意我们再背包中添加时是倒序的(为了避免重复)，我们再删时，为了避免减多，需要正序减。
void add(int x,int y){
for(int i=N;i>=y;i--) update(dp[x][i],dp[x][i-y],1);
}
void del(int x,int y){
for(int i=y;i<=N;i++) update(dp[x][i],dp[x][i-y],0);
}
而询问时，由于 d p i , j dp_{i,j} dpi,j 只考虑了点 i i i 的儿子，故我们可以将 a f a i a_{fa_i} afai 添入 d p i , j dp_{i,j} dpi,j 中，输出完后再删去即可。
Code：
#include<bits/stdc++.h>
#define mod 998244353
using namespace std;
const int N=4000;
int a[N+10],fa[N+10];
long long dp[N+10][N+10];
int n,q;
void update(long long&x,long long y,int f){
if(f) x+=y;
else x-=y;
if(x>=mod) x-=mod;
if(x<0) x+=mod;
}
void add(int x,int y){
for(int i=N;i>=y;i--) update(dp[x][i],dp[x][i-y],1);
}
void del(int x,int y){
for(int i=y;i<=N;i++) update(dp[x][i],dp[x][i-y],0);
}
int main(){
scanf("%d%d",&n,&q);
a[0]=N+10;
for(int i=2;i<=n;i++) scanf("%d",&fa[i]);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
dp[i][0]=1;
}
for(int i=2;i<=n;i++) add(fa[i],a[i]);
while(q--){
int opt,x,y;
scanf("%d%d%d",&opt,&x,&y);
if(opt==1){
del(fa[x],a[x]);
a[x]=y;
add(fa[x],a[x]);
}
else{
add(x,a[fa[x]]);
printf("%lld\n",dp[x][y]);
del(x,a[fa[x]]);
}
}
return 0;
}