题解

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=100010;
const int mod=998244353;
int n,m,Q,tot,head[N],a[N],ind[N],dp[N];
int f[N],op[N],pos[N],add[N],cnt[N],gson[N];
vector<int>e[N],suffix[N];
queue<int>q;bool vis[N];
int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x10+ch-'0';ch=getchar();}
return xf;
}
void add_edge(int u,int v)
{
e[u].push_back(v);
ind[v];
}
void init(int u)
{
vis[u]=1;
if(op[u]==1) suffix[u].push_back(1);
else if(op[u]==2) suffix[u].push_back(add[u]);
else
{
suffix[u].resize(e[u].size());
for(int i=0;i<e[u].size();i)
{
int v=e[u][i];
if(!vis[v]) init(v);
suffix[u][i]=suffix[v][0];
}
for(int i=e[u].size()-2;i>=0;i--)
suffix[u][i]=suffix[u][i]*suffix[u][i+1]%mod;
}
}
void topo()
{
for(int i=1;i<=m;i++) if(!ind[i]) q.push(i);
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=0;i<e[u].size();i++)
{
int v=e[u][i];
ind[v]--;
if(!ind[v]) q.push(v);
if(!vis[u]) continue;
if(i<e[u].size()-1)
dp[v]=(dp[v]+dp[u]*suffix[u][i+1]%mod)%mod;
else dp[v]=(dp[v]+dp[u])%mod;
}
}
}
signed main()
{
n=read();
for(int i=1;i<=n;i++) a[i]=read();
m=read();
for(int i=1;i<=m;i++)
{
op[i]=read();
if(op[i]==1)
{
pos[i]=read();
add[i]=read();
}
else if(op[i]==2)
{
add[i]=read();
}
else if(op[i]==3)
{
cnt[i]=read();
for(int j=1;j<=cnt[i];j++)
{
gson[j]=read();
add_edge(i,gson[j]);
}
}
}
m++;
Q=read();
for(int i=1;i<=Q;i++)
{
f[i]=read();
add_edge(m,f[i]);
}
init(m);
dp[m]=1; topo();
for(int i=1;i<=n;i++) a[i]=a[i]*suffix[m][0]%mod;
for(int i=1;i<=m;i++)
{
if(op[i]==1)
{
a[pos[i]]=(a[pos[i]]+add[i]*dp[i]%mod)%mod;
}
}
for(int i=1;i<=n;i++)
printf("%lld ",a[i]%mod);
return 0;
}