[ARC121F] Logical Operations on Tree 题解

题目链接

点击打开链接

题目解法

比较好的题

首先要发现一个性质是：先删 AND 边，再删 OR 边最优
小证一下：分类讨论 AND 边两端的数字情况

1. \(0 \& 0\)
   左右两端虽然可能可以把 \(1\) OR 过来，但这种情况先做 \(\&\)，也一定可以 OR 得到 \(1\)
2. \(0 \& 1\)
   左边可能可以 \(OR\) 得到 \(1\)，但和上面的情况同理，先做 \(\&\)，一定可以按照同样的线路 OR 得到 \(1\)
3. \(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;
}