C++14(g++5.4) 解法, 执行用时: 896ms, 内存消耗: 6264K, 提交时间: 2019-07-10 21:28:43

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int gi(){
	int x=0,w=1;char ch=getchar();
	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
	if(ch=='-')w=0,ch=getchar();
	while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	return w?x:-x;
}
const int N=1e5+5;
const int mod=1e9+7;
int n,m,fa[N],f[N][13],s[N];
int fastpow(int x,int y){
	int res=1;
	while(y){if(y&1)res=1ll*res*x%mod;x=1ll*x*x%mod;y>>=1;}
	return res;
}
void work(int x,int y){
	for(int i=10;i;--i)
		for(int j=1;i+j<=10;++j)
			f[x][i+j]=(f[x][i+j]+1ll*f[x][i]*f[y][j])%mod;
}
void undo(int x,int y){
	for(int i=1;i<=10;++i)
		for(int j=1;i+j<=10;++j)
			f[x][i+j]=(f[x][i+j]+1ll*(mod-f[x][i])*f[y][j])%mod;
}
int main(){
	n=gi();m=gi();
	for(int i=1;i<=n;++i)f[i][1]=gi();
	for(int i=2;i<=n;++i)fa[i]=gi();
	for(int i=n;i>1;--i)work(fa[i],i);
	while(m--)
		if(gi()){
			int x=gi(),y=gi(),top=0;
			for(int i=x;i;i=fa[i])s[++top]=i;
//			for(int i=1;i<=top;++i)printf("%d ",s[i]);puts("");
//			for(int i=1;i<=10;++i)printf("%d ",f[1][i]);puts("");
//			for(int i=1;i<=10;++i)printf("%d ",f[2][i]);puts("");
			for(int i=top-1;i;--i)undo(s[i+1],s[i]),work(s[i],s[i+1]);
//			for(int i=1;i<=10;++i)printf("%d ",f[1][i]);puts("");
//			for(int i=1;i<=10;++i)printf("%d ",f[2][i]);puts("");
			printf("%d\n",f[x][y]);
			for(int i=1;i<top;++i)undo(s[i],s[i+1]),work(s[i+1],s[i]);
		}else{
			int x=gi(),y=gi(),top=0;
			for(int i=x;i;i=fa[i])s[++top]=i;
			for(int i=top-1;i;--i)undo(s[i+1],s[i]);
			y=1ll*y*fastpow(f[x][1],mod-2)%mod;
			for(int i=1;i<=10;++i)f[x][i]=1ll*f[x][i]*y%mod;
			for(int i=1;i<top;++i)work(s[i+1],s[i]);
		}
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 1393ms, 内存消耗: 20864K, 提交时间: 2018-01-19 21:38:06

#include<bits/stdc++.h>
using namespace std;

template <typename T> void chmax(T &x,const T &y)
{
	if(x<y)x=y;	
}

typedef long long ll;
#define rep(i,l,r) for(int i=l;i<=r;++i)
#define per(i,r,l) for(int i=r;i>=l;--i)
const int N=1e5+5,S=10+1;
const int D=1e9+7;
ll MI(ll x,int y,int D)
{
	ll ans=1;
	while(y)
	{
		if(y&1)ans=ans*x%D;
		x=x*x%D;y>>=1;
	}
	return ans;
}
int fa[N],t[N],v[N];
struct edge
{
	int to,next;
};
edge l[N*2];int e;
ll dp[N][S];
ll DP[N][S];

ll *dfs(int x,int s,int fr)
{
	if(fr==fa[x])return DP[x];
	dp[x][1]=v[x];
	if(s==1)return dp[x];
	rep(j,2,s)dp[x][j]=0;
	for(int i=t[x];i;i=l[i].next)
	{
		int y=l[i].to;
		if(y==fr)continue;
		ll *dpy=dfs(y,s-1,x);
		per(j,s,2)
		rep(k,1,j-1)(dp[x][j]+=dp[x][k]*dpy[j-k])%=D;
	}
	return dp[x];
}
void up(int x)
{
				rep(j,2,S-1)	DP[x][j]=0;
					for(int i=t[x];i;i=l[i].next)
					{
						int y=l[i].to;
						if(y==fa[x])continue;
						per(j,S-1,2)
						rep(k,1,j-1)(DP[x][j]+=DP[x][k]*DP[y][j-k])%=D;
					}
}
int main()
{
	//freopen("1.in","r",stdin);
	int n,tt;
	cin>>n>>tt;
	rep(i,1,n)scanf("%d",v+i);
	rep(i,2,n)
	{
		scanf("%d",&fa[i]);
		l[++e]=(edge){i,t[fa[i]]};t[fa[i]]=e;
		l[++e]=(edge){fa[i],t[i]};t[i]=e;
	}
	per(i,n,1)
	{
		DP[i][1]=v[i];
		up(i);
	}

	while(tt--)
	{
		int op;
		scanf("%d",&op);
		if(op==0)
		{
			int x,c;
			scanf("%d%d",&x,&c);
			DP[x][1]=v[x]=c;
			for(;x;x=fa[x])
			{
				up(x);
			}
		}
		else
		{
			int k,s;
			scanf("%d%d",&k,&s);
			//dfs(k,s,0);
			printf("%d\n",dfs(k,s,0)[s]);
		}
	}
}