whiteqwq @ 2020-11-12 18:20:33
```
#include<stdio.h>
#include<queue>
#include<vector>
#define int long long
using namespace std;
const int maxn=100005,maxm=1000005,mod=998244353;
int n,m,Q,e,all;
int a[maxn],t[maxn],c[maxn],v[maxn],p[maxn],deg[maxn],mul[maxn],add[maxn],s[maxn],tag[maxn];
queue<int>q;
vector<int>g[maxn];
void dfs(int x){
mul[x]=(t[x]==2? v[x]:1);
for(int i=0;i<g[x].size();i++){
int y=g[x][i];
if(mul[y]==0)
dfs(y);
mul[x]=mul[x]*mul[y]%mod;
}
}
void pre(){
int now=1;
for(int i=Q;i>=1;i--){
tag[s[i]]=now;
now=now*mul[s[i]]%mod;
}
all=now;
}
void topo(){
for(int i=1;i<=m;i++)
if(deg[i]==0)
q.push(i);
while(!q.empty()){
int x=q.front();
q.pop();
if(t[x]==1)
add[p[x]]=(add[p[x]]+v[x]*tag[x]%mod)%mod;
if(t[x]==3){
int now=tag[x];
for(int i=g[x].size()-1;i>=0;i--){
int y=g[x][i];
tag[y]=(tag[y]+now)%mod;
now=now*mul[y]%mod;
deg[y]--;
if(deg[y]==0)
q.push(y);
}
}
}
}
signed main(){
scanf("%lld",&n);
for(int i=1;i<=n;i++)
scanf("%lld",&a[i]);
scanf("%lld",&m);
for(int i=1;i<=m;i++){
scanf("%lld",&t[i]);
if(t[i]==1)
scanf("%lld%lld",&p[i],&v[i]);
if(t[i]==2)
scanf("%lld",&v[i]);
if(t[i]==3){
scanf("%lld",&c[i]);
for(int j=1;j<=c[i];j++){
int k;
scanf("%lld",&k);
g[i].push_back(k),deg[k]++;
}
}
}
for(int i=1;i<=m;i++)
if(mul[i]==0)
dfs(i);
scanf("%lld",&Q);
for(int i=1;i<=Q;i++)
scanf("%lld",&s[i]);
pre(),topo();
for(int i=1;i<=n;i++)
printf("%lld%c",(a[i]*all%mod+add[i])%mod,i==n? '\n':' ');
return 0;
}
```
by whiteqwq @ 2020-11-18 22:10:27
pre是设定初始值没关系的 @四旬老汉
顺带封贴。
WA原因：
void dfs(int x){
mul[x]=(t[x]==2? v[x]:1);
for(int i=0;i<g[x].size();i++){
int y=g[x][i];
if(mul[y]==0)
dfs(y);
mul[x]=mul[x]*mul[y]%mod;
}
}
函数中没有乘\text{1ll}，应改为：
mul[x]=1ll*mul[x]*mul[y]%mod;
TLE原因：\text{dfs}中没有加vis标记