题目链接
题目解法
比较好的题
首先要发现一个性质是：先删 AND 边，再删 OR 边最优
小证一下：分类讨论 AND 边两端的数字情况
- \(0 \& 0\)
左右两端虽然可能可以把 \(1\) OR 过来，但这种情况先做 \(\&\)，也一定可以 OR 得到 \(1\) - \(0 \& 1\)
左边可能可以 \(OR\) 得到 \(1\)，但和上面的情况同理，先做 \(\&\)，一定可以按照同样的线路 OR 得到 \(1\) - \(1 \& 1\)
先 \(\&\) 可以防止后面缩的时候变成 \(0\)，而且先 \(\&\) 不会使树的形态变劣
所以我们可以删去 \(|\) 边，得到一些只有 \(\&\) 边的连通块，不难得到合法的充要条件为其中必须有一个连通块权值都为 \(1\)
不难树形 \(dp\)，容斥一下求不合法的方案数会使 \(dp\) 更简单
时间复杂度 \(O(n)\)
#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
template<typename T> void read(T &FF){
FF=0;int RR=1;
char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
FF*=RR;
}
const int N=100100,P=998244353;
int n,f[N][2];
int e[N<<1],ne[N<<1],h[N],idx;
void dfs(int u,int fa){
f[u][0]=f[u][1]=1;
for(int i=h[u];~i;i=ne[i]){
int v=e[i];if(v==fa) continue;
dfs(v,u);
int t0=f[u][0],t1=f[u][1];
f[u][0]=(1ll*t0*f[v][1]+1ll*t0*f[v][0])%P;
f[u][1]=(1ll*t1*(f[v][0]+f[v][1])+1ll*t0*f[v][1]+1ll*t1*f[v][1])%P;
}
}
void add(int x,int y){ e[idx]=y,ne[idx]=h[x],h[x]=idx++;}
int main(){
read(n);ms(h,-1);
F(i,1,n-1){
int x,y;read(x),read(y);
add(x,y),add(y,x);
}
dfs(1,-1);
int tot=1;
F(i,1,2*n-1) tot=tot*2%P;
printf("%d\n",(tot-f[1][1]+P)%P);
return 0;
}