Description

Input

Output

输出文件名为 call.out。

Sample Input

Sample Input1
3
1 2 3
3
1 1 1
2 2
3 2 1 2
2
2 3


Sample Input2
10
1 2 3 4 5 6 7 8 9 10
8
3 2 2 3
3 2 4 5
3 2 5 8
2 2
3 2 6 7
1 2 5
1 7 6
2 3
3
1 2 3
 

Sample Output

Sample Output1
6 8 12 


Sample Output2
36 282 108 144 180 216 504 288 324 360 
 

Data Constraint

Solution

考虑计算每个加函数对答案的贡献。模拟下暴力的过程，显然它的贡献取决于操作它之后会乘多少。

先对于每个节点，计算出包含它的最小闭合子图（类比子树）的乘积，记作 p i。

对于某个节点 u，从后往前枚举边 v i，可以发现对 v i 的贡献为    。不过这个只是在包含 u 的最小闭 合子图中的贡献，实际上的贡献还要乘上u 的调用次数。

于是具体的做法就出来了：按照拓扑序来做，每个节点上记个 tag i ，表示i 的调用次数。做到节点 u 时，枚举边算贡献，乘上tag i ，然后加到贡献到的节点上去。

时间复杂度是线性的。

考虑答案一定是对整个序列同时乘以了一个相同数，再对每个位置上加上一个不同的数。

乘的值就为所有乘操作的乘积，拓扑排序后从后往前推可以得到。

对于每一个位置加上的数，即为这个位置原本要加的数（读入的数），乘以这个操作后面的所有乘操作的乘积。

那么就处理出所有当前操作后面的乘积，同样用拓扑排序后配合前向星（可以达到按照操作顺序从后往前做的效果，以此来处理后缀积）递推得到，注意计算兄弟的贡献。

最后对于每一个位置上的a加上要加的值即可。

Code 

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define I int
#define ll long long
#define F(i,a,b) for(register I i=a;i<=b;i++)
#define Fd(i,a,b) for(register I i=a;i>=b;i--)
#define N 100005
#define M 1000004
#define mo 998244353
using namespace std;
I n,m,a[N],f[N],op[N],b[N],v[N],c[N],q[M],r,x,s;
I t[M<<1],nx[M<<1],ls[M],d[M],tot,p;
I R(I &x){
	x=0;char c=getchar();
	while(c<'0'||c>'9') c=getchar();
	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
	return x;
}
void add(I x,I y){
	d[t[++tot]=y]++,nx[tot]=ls[x],ls[x]=tot;
}
I main(){
	freopen("call.in","r",stdin);
	freopen("call.out","w",stdout);
	R(n);
	F(i,1,n) R(a[i]);
	R(m);
	F(i,1,m){
		R(op[i]);
		if(op[i]==1){R(b[i]),R(v[i]);}
		else if(op[i]==2) R(v[i]);
		else{
			R(p);
			while(p--) add(i,R(x));
		}
	}
	R(p);
	F(i,1,p) add(0,R(x));
	F(i,0,m) if(!d[i]) q[++r]=i;//注意n和m千万不要打反，不然可能少了那么40分左右
	F(i,1,r){
		x=q[i];
		for(I k=ls[x];k;k=nx[k]) if(!--d[t[k]]) q[++r]=t[k];
	}
	Fd(i,r,1){
		x=q[i];
		d[x]=op[x]==2?v[x]:1;
		for(I k=ls[x];k;k=nx[k]) d[x]=(ll)d[x]*d[t[k]]%mo;
	}
	F(i,1,n) a[i]=(ll)a[i]*d[0]%mo;
	f[0]=1;
	F(i,1,r){
		x=q[i];
		s=1;
		for(I k=ls[x];k;k=nx[k]){
			f[t[k]]=(ll)(f[t[k]]+(ll)s*f[x]%mo)%mo;//注意这个加法操作可能有多个父亲，
//从每个父亲走到这里都加了一遍，所以是所有父亲的后继积分别乘以这个加法操作再求和 
			s=(ll)s*d[t[k]]%mo;
		}
		if(op[x]==1) a[b[x]]=(ll)(a[b[x]]+(ll)f[x]*v[x]%mo)%mo;
	}
	F(i,1,n) printf("%d ",a[i]);
	return 0;
}