链接：https://www.nowcoder.com/acm/contest/57/F
时间限制：C/C++ 2秒，其他语言4秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
64bit IO Format: %lld
题目描
白云有一棵n个结点的树，以1号结点为根，这棵树的每个结点有一个权值vali
定义一个连通块的喜爱度为块内所有结点权值的乘积。
白兔有很多疑问，每个疑问有两个参数k,s，表示询问所有经过点k的大小为s的连通块的喜爱度之和。
白云会定期对树做一些修改。
白云会定期对树做一些修改。
输入描述:
第一行1个整数n,Q，表示树的结点个数和事件个数。
第二行n个整数表示val
1 ... n
。
第三行n-1个整数表示2...n号结点的父亲。
接下来Q行，第一个数为op∈{0,1}，
如果op=0表示白云要对某个结点的权值进行修改，接下来两个数k,c表示把结点k的权值修改为c。
如果op=1表示白兔的疑问，接下来两个数k,s。
输出描述:
对于op=1，每行一个数表示答案。答案对1e9+7
取模。
输入例子:
15 15
6 4 8 6 8 9 10 9 2 9 8 3 3 6 2
1 1 1 3 1 3 6 5 3 10 9 7 9 13
1 13 8
1 2 4
1 12 8
1 11 2
0 2 9
0 11 4
1 3 6
0 4 5
1 13 7
1 8 2
1 7 6
1 7 8
0 5 5
0 1 7
1 1 6
输出例子:
128592000
11304
35520768
72
10402608
16325280
81
6030720
359079840
8686888
-->
示例1
输入
15 15
6 4 8 6 8 9 10 9 2 9 8 3 3 6 2
1 1 1 3 1 3 6 5 3 10 9 7 9 13
1 13 8
1 2 4
1 12 8
1 11 2
0 2 9
0 11 4
1 3 6
0 4 5
1 13 7
1 8 2
1 7 6
1 7 8
0 5 5
0 1 7
1 1 6
输出
128592000
11304
35520768
72
10402608
16325280
81
6030720
359079840
8686888
备注:
结点k的父亲为1...k-1的一个均匀随机整数。
vali∈[1,109+7),s≤10,n,Q≤10^5
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
题解：
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
#include <bits/stdc++.h>
#define mst(a,b) memset((a),(b), sizeof a)
#define lowbit(a) ((a)&(-a))
#define IOS ios::sync_with_stdio(0);cin.tie(0);
#define MP make_pair
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int mod=1e9+;
const int maxn=1e5+;
ll dp[maxn][];
int val[maxn],fa[maxn];
vector<int>son[maxn];
int qpow(ll a,int b){
ll res=;
while(b){
if(b&)res=res*a%mod;
b>>=;
a=a*a%mod;
}
return res;
}
void add(int a,int b){
for(int i=;i;--i)
for(int j=;j<i;++j)
dp[a][i]=(dp[a][i]+dp[b][j]*dp[a][i-j])%mod; }
void del(int a,int b){
for(int i=;i<=;++i)
for(int j=;j<i;++j)
dp[a][i]=(dp[a][i] - dp[b][j]*dp[a][i-j])%mod;
}
void dfs(int pos){
dp[pos][]=;dp[pos][]=val[pos];
for(int i=;i<son[pos].size();++i){
int to=son[pos][i];
dfs(to);
add(pos,to);
}
}
void update_1(int pos){
if(pos==)return;
update_1(fa[pos]);
del(fa[pos],pos);
}
void update_2(int pos){
if(pos==)return;
add(fa[pos],pos);
update_2(fa[pos]);
}
void update(int k,int c){
update_1(k);
int cc=qpow(val[k],mod-);
for(int i=;i<=;++i)
dp[k][i]=dp[k][i]*cc%mod*c%mod;
val[k]=c;
update_2(k);
}
ll dd[][];
int now;
void qq(int pos,int s){
if(pos!=)qq(fa[pos],pos);
now^=;
memcpy(dd[now],dp[pos],sizeof dp[pos]);
for(int i=;i<=;++i)
for(int j=;j<i;++j)
dd[now][i]=(dd[now][i] - dp[s][j]*dd[now][i-j])%mod;
if(pos!=){
for(int i=;i;--i)
for(int j=;j<i;++j)
dd[now][i]=(dd[now][i]+dd[now^][j]*dd[now][i-j])%mod;
}
}
int query(int k,int s){
if(k==)return (dp[k][s]+mod)%mod;
int f=fa[k];
qq(f,k);
ll ret=;
for(int i=;i<s;++i)
ret=(ret+dd[now][i]*dp[k][s-i])%mod;
return (ret+mod)%mod;
}
int main(){
#ifdef local
freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
#endif
int n,q;scanf("%d%d",&n,&q);
for(int i=;i<=n;++i)scanf("%d",&val[i]);
for(int i=;i<=n;++i){
scanf("%d",&fa[i]);
son[fa[i]].push_back(i);
}
dfs();
while(q--){
int op,a,b;scanf("%d%d%d",&op,&a,&b);
if(op)printf("%d\n",query(a,b));
else update(a,b);
}
return ;
}
首先是随机树的树高是logn这点是不知道的，所以看到题就是蒙圈的，这点是学到了
然后在码的过程中update那个函数，里面对于k点dp值的更新我一开始是这样的
for(int i=;i<=;++i){
dp[k][i]=(dp[k][i]-val[k]*dp[k][i-])%mod;
dp[k][i]=(dp[k][i]+mod)%mod;
}
val[k]=c;
for(int i=;i;--i){
dp[k][i]=(dp[k][i]+dp[k][i-]*val[k])%mod;
}
错的很离谱，引以为鉴