本题一开始读错题了，把题目加强了好多。（
本题有经典的去叶子归纳法，值得学习。
考虑知道了标号之后怎么判断合法。
考虑一个叶子和其连向父亲的边。
如果边是 OR，点是 ，原问题一定有解。
如果边是 OR，点是 ，或者边是
AND，点是 ，那这个叶子对答案没有影响，可以直接舍弃。
如果边是 AND，点是 ，要尽量早的把这个叶子缩掉，这样对后面的危害最小。
把这个步骤由深往浅的归纳，就会发现，我们对一棵子树只需要记录两个信息：最终的权值，以及有没有一个连通块向外恰好连了一条
OR 边 且最终权值为 。
说白了就是记录在整个过程中，有没有出现 "OR 1" 型的叶子。
设出状态 表示 子树的最终权值为 / 为 且没有 "OR 1" 型叶子 / 有 "OR 1"
型叶子。
那么状态转移如下： 第一行： and ，
or ， and ，
and 。
第二行： 因为没有 "OR 1" 型叶子， 子树必须是 "AND 1" 或者 "OR 0"，那么
所属连通块权值必然为 。
第三行：前面是任意一侧有 "OR 1" 型叶子的情况，后面是 子树是 "OR 1" 型叶子的情况。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| #include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5,P = 998244353;
inline int Add(int a,int b) { return (a + b >= P) ? (a + b - P) : (a + b);}
int n;
vector<int> G[N];
int f[N][3];
void dp(int x,int fa)
{
f[x][0] = f[x][1] = 1;
for(auto y : G[x])
{
if(y == fa) continue;
dp(y,x);
int v0 = f[x][0],v1 = f[x][1],v2 = f[x][2];
f[x][2] = Add(2ll * v2 * Add(f[y][2],Add(f[y][0],f[y][1])) % P,Add(2ll * f[y][2] * (v0 + v1) % P,1ll * f[y][1] * (v0 + v1) % P));
f[x][0] = Add(Add(2ll * v0 * f[y][0] % P , 1ll * v0 * f[y][1] % P),1ll * v1 * f[y][0] % P);
f[x][1] = 1ll * v1 * (f[y][1] + f[y][0]) % P;
}
}
int main()
{
cin >> n;
for(int i = 1;i < n;i++)
{
int x,y;
cin >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
dp(1,0);
cout << Add(f[1][1],f[1][2]) << endl;
return 0;
}
|