[DP记录]ARC121F Logical Operations on Tree
command_block
2021-10-28 22:04:08
**题意** ： 给定一棵树，现在需要为每一个点填写权值 $w_u\in\{0,1\}$，每条边填写运算 $op_l=\{\rm AND,OR\}$ 。
填写完后，每次可以选择一条边 $l:(u,v)$ 收缩，收缩产生的新点权值为 $w_u\ op_l\ w_v$ 。（其中 $op_l$ 是运算）
对于所有 $2^{2n−1}$ 种填写方案，求满足“存在一种收缩顺序使得最终剩余的点权值为 $1$”的方案数。
$n\leq 10^5$ ，时限$\texttt{2s}$。
------------
先考虑给定填写情况，如何判定是否存在一种收缩顺序，使得最终剩余的点权值为 $1$ 。
考虑一个叶子：（经典的去叶子归纳法）
- 若父边是 $\rm OR$ ，权值是 $1$ ，则必有解。
- 若父边是 $\rm OR$ ，权值是 $0$ ，对答案无影响，直接去掉。
- 若父边是 $\rm AND$ ，权值是 $1$ ，则先处理其余部分，最后收缩。
- 若父边是 $\rm AND$ ，权值是 $0$ ，则必定会将父亲置 $0$ 一次，不妨首先收缩，这样危害最小。
按照这个策略从深往浅做就是，每个子树只会保留两条信息：最终权值，是否含 $\rm OR\ 1$ 。
然后考虑 DP ：
记 $f_{u,0/1/2}$ 表示 $u$ 子树内 权值为 $0$ / 权值为 $1$ 但不含 $\rm OR\ 1$ / 含 $\rm OR 1$ （且权值为 $1$） 的方案数。
当将子树 $v$ 加入 $u$ 时根据上述策略，能写出转移 ：
$$
\begin{aligned}
f_{u,0}'&=2f_{u,0}f_{v,0}+f_{u,1}f_{v,0}+f_{u,0}f_{v,1}\\
f_{u,1}'&=f_{u,1}(f_{v,1}+f_{v,0})\\
f_{u,2}'&=f_{u,2}(f_{v,0}+f_{v,1}+f_{v,2})+f_{v,2}(f_{u,0}+f_{u,1})+f_{v,1}(f_{u,1}+f_{u,0})
\end{aligned}
$$
- 第一行 ： $0{\ \rm or\ }0,\ 0{\ \rm and\ }0,\ 1{\ \rm and\ }0,\ 0{\ \rm and\ }1$ 。
- 第二行 ： $1{\ \rm and\ }1,\ 1{\ \rm or\ }1$ 。
- 第三行 ： 任意一侧有 $\rm or\ 1$ ，与 $0{\ \rm or\ }1,\ 1{\ \rm or\ }1$ 。
复杂度 $O(n)$。
```cpp
#include<algorithm>
#include<cstdio>
#define ll long long
#define pb push_back
#define MaxN 200500
using namespace std;
const int mod=998244353;
vector<int> g[MaxN];
int f[MaxN][3];
void dfs(int u,int fa)
{
f[u][0]=f[u][1]=1;
for (int i=0,v;i<g[u].size();i++)
if ((v=g[u][i])!=fa){
dfs(v,u);
int s0=f[u][0],s1=f[u][1],s2=f[u][2];
f[u][0]=(2ll*s0*f[v][0]+1ll*s1*f[v][0]+1ll*s0*f[v][1])%mod;//4
f[u][1]=1ll*s1*(f[v][1]+f[v][0])%mod;//2
f[u][2]=((s2*((ll)f[v][0]+f[v][1]+f[v][2])+1ll*f[v][2]*(s0+s1))%mod*2+1ll*f[v][1]*(s0+s1))%mod;//12
}
}
int n;
int main()
{
scanf("%d",&n);
for (int i=1,u,v;i<n;i++){
scanf("%d%d",&u,&v);
g[u].pb(v),g[v].pb(u);
}dfs(1,0);
printf("%d",(f[1][1]+f[1][2])%mod);
return 0;
}
```