树形\(DP\)
实际上，这道题应该不是很难。
我们设\(f_{x,i,j}\)表示在以\(x\)为根的子树内，原本应输出\(i\)，结果输出了\(j\)的情况数。
转移时，为了方便，我们先考虑与，再考虑非，即先转移，再交换\(f_{x,0,0}\)和\(f_{x,1,1}\)，\(f_{x,1,0}\)和\(f_{x,0,1}\)。
这样一来，转移方程如下：
\[f_{x,i1\&i2,j1\&j2}=\sum f_{x,i1,j1}*f_{son,i2,j2}\]
然后，在转移结束，交换完毕之后，我们还要判断这点是否出故障。
若\(op_x=0\)，我们令\(f_{x,0,0}=f_{x,0,0}+f_{x,0,1},f_{x,1,0}=f_{x,1,0}+f_{x,1,1},f_{x,0,1}=f_{x,1,1}=0\)，\(op_x=1\)同理。
注意最后答案为\(\frac{f_{rt,0,0}+f_{rt,1,1}}{2^{\sum g_i}}\)，且\(\sum g_i\)千万不能向\(998244353\)取模！我一开始智障地取了模，调了1个小时，最后还是左右横调才调出来的。。。
代码
#include#define Tp template #define Ts template #define Reg register#define RI Reg int#define Con const#define CI Con int&#define I inline#define W while#define N 200000#define X 998244353#define LL long long#define swap(x,y) (x^=y^=x^=y)#define Qinv(x) Qpow(x,X-2)#define Inc(x,y) ((x+=(y))>=X&&(x-=X))#define add(x,y) (e[++ee].nxt=lnk[x],e[lnk[x]=ee].to=y)using namespace std;int n,rt,ee,g[N+5],op[N+5],lnk[N+5];struct edge {int to,nxt;}e[N];class FastIO{ private: #define FS 100000 #define tc() (A==B&&(B=(A=FI)+fread(FI,1,FS,stdin),A==B)?EOF:*A++) #define tn (x<<3)+(x<<1) #define D isdigit(c=tc()) int f;char c,*A,*B,FI[FS]; public: I FastIO() {A=B=FI;} Tp I void read(Ty& x) {x=0,f=1;W(!D) f=c^'-'?1:-1;W(x=tn+(c&15),D);x*=f;} Ts I void read(Ty& x,Ar&... y) {read(x),read(y...);} #undef D}F;class TreeDper//树形DP{ private: int Sz[N+5],f[N+5][2][2],f_[2][2]; I int Qpow(RI x,LL y) {RI t=1;W(y) y&1&&(t=1LL*t*x%X),x=1LL*x*x%X,y>>=1;return t;}//快速幂 I void Init(CI x)//初始化，将g[i]减去已有子节点个数 { for(RI i=(Sz[x]=0,lnk[x]);i;i=e[i].nxt) Init(e[i].to),++Sz[x]; g[x]-=Sz[x]; } I void DP(CI x)//树形DP { if(!lnk[x]) return (void)(f[x][0][~op[x]?op[x]:0]=1,f[x][1][~op[x]?op[x]:1]=Qpow(2,g[x])-1);//特殊处理叶节点 RI i,xx,xy,yx,yy;for(f[x][0][0]=Qpow(2,g[x])-1,f[x][1][1]=1,i=lnk[x];i;i=e[i].nxt)//枚举子节点 { DP(e[i].to),f_[0][0]=f_[0][1]=f_[1][0]=f_[1][1]=0;//注意此处要开一个中间数组 for(xx=0;xx^2;++xx) for(xy=0;xy^2;++xy) for(yx=0;yx^2;++yx) for(yy=0;yy^2;++yy) f_[xx&yx][xy&yy]=(1LL*f[x][xx][xy]*f[e[i].to][yx][yy]+f_[xx&yx][xy&yy])%X;//转移 f[x][0][0]=f_[0][0],f[x][0][1]=f_[0][1],f[x][1][0]=f_[1][0],f[x][1][1]=f_[1][1];//更新信息 } swap(f[x][0][0],f[x][1][1]),swap(f[x][0][1],f[x][1][0]),//交换 op[x]==0&&(Inc(f[x][0][0],f[x][0][1]),Inc(f[x][1][0],f[x][1][1]),f[x][0][1]=f[x][1][1]=0),//特判op[x]=0 op[x]==1&&(Inc(f[x][1][1],f[x][1][0]),Inc(f[x][0][1],f[x][0][0]),f[x][1][0]=f[x][0][0]=0);//特判op[x]=1 } public: I void Solve() { RI i;LL sg=0;for(Init(rt),i=1;i<=n;++i) sg+=g[i];DP(rt);//统计Σg[i] printf("%d",1LL*(f[rt][0][0]+f[rt][1][1])*Qinv(Qpow(2,sg))%X);//输出答案 }}D;int main() { freopen("nand.in","r",stdin),freopen("nand.out","w",stdout); RI i,x;for(F.read(n),i=1;i<=n;++i) F.read(x,g[i],op[i]),x?add(x,i):rt=i;//读入数据 return D.Solve(),0;}