（特判$n=1$的情况）
当确定权值和操作后，如何判定是否合法——
考虑一个度为1的节点，对其权值即其对应边的边操作分类讨论：
$1or$，显然只需要最后选择这条边即可，一定合法
$1and$或$0or$，显然这条边没有意义，不妨直接选择
$0and$，将最终的结果变为0，显然不如初始的值为0（结果仍为0也不劣），因此也不妨直接选择
综上，有以下策略：若存在$1or$的情况一定合法，否则不断选择某一条度为1的点对应的边即可
然后，进行树形dp即可，令$f_{k,0/1/2}$表示以$k$为根的子树中最终$k$的权值为0/1且未出现$1or$的情况和出现$1or$的方案数（仅考虑子树内部），转移即
$$
egin{cases}f_{k,0}=f_{k,0}(2f_{son,0}+f_{son,1})+f_{k,1}f_{son,0}\f_{k,1}=f_{k,1}(f_{son,0}+f_{son,1})\f_{k,2}=(f_{k,0}+f_{k,1})(f_{son,1}+2f_{son,2})+2f_{k,2}(f_{son,0}+f_{son,1}+f_{son,2})end{cases}
$$
初始状态为$f_{k,0}=f_{k,1}=1$，最终答案为$f_{rt,1}+f_{rt,2}$
时间复杂度为$o(n)$，可以通过
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 100005 4 #define mod 998244353 5 #define ll long long 6 struct Edge{ 7 int nex,to; 8 }edge[N<<1]; 9 int E,n,x,y,ans,head[N]; 10 ll g[3],f[N][3]; 11 void add(int x,int y){ 12 edge[E].nex=head[x]; 13 edge[E].to=y; 14 head[x]=E++; 15 } 16 void dfs(int k,int fa){ 17 f[k][0]=f[k][1]=1; 18 for(int i=head[k];i!=-1;i=edge[i].nex){ 19 int v=edge[i].to; 20 if (v!=fa){ 21 dfs(v,k); 22 memcpy(g,f[k],sizeof(g)); 23 f[k][0]=(g[0]*(2*f[v][0]+f[v][1])+g[1]*f[v][0])%mod; 24 f[k][1]=g[1]*(f[v][0]+f[v][1])%mod; 25 f[k][2]=((g[0]+g[1])*(f[v][1]+2*f[v][2])%mod+2*g[2]*(f[v][0]+f[v][1]+f[v][2]))%mod; 26 } 27 } 28 } 29 int main(){ 30 scanf("%d",&n); 31 memset(head,-1,sizeof(head)); 32 for(int i=2;i<=n;i++){ 33 scanf("%d%d",&x,&y); 34 add(x,y); 35 add(y,x); 36 } 37 dfs(1,0); 38 printf("%d",(f[1][1]+f[1][2])%mod); 39 }