自从上次模拟赛后，我决定隔一段时间整理一些背包优化，可能毫无顺序
1.
d
f
s
dfs
dfs的时候保存链的信息
一道模拟赛题：给定一棵树，有
n
n
n各节点，每个节点都有一个非负权值，对于每条边，你有
0.5
0.5
0.5的概率断掉这条边，求以
1
1
1为根遍历的数的权值之和为
k
k
k的概率（答案对
998244353
998244353
998244353取模）
1
<
=
n
,
k
<
=
5000
1 <= n,k <= 5000
1<=n,k<=5000 直接设
d
p
[
i
]
[
j
]
dp[i][j]
dp[i][j]代表以
i
i
i为根的子树权值之和为
k
k
k的概率，这样
d
p
dp
dp的复杂度是
O
(
n
3
)
O(n^3)
O(n3) 那么怎么优化呢，我们只需设
d
p
[
i
]
[
j
]
dp[i][j]
dp[i][j]为遍历完以
i
i
i为根的子树，权值之和为
k
k
k的概率 注意，这两个状态的不同是第二个状态也记录了从
1
1
1走到
i
i
i的情况（因为遍历是从
1
1
1开始的） 具体转移看代码即可
C
o
d
e
Code
Code
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
using namespace std
;
#define int long long
const int MAXN
= 5000, P
= 499122177, Mod
= 998244353;
struct w
{
int to
, nx
;
}head
[MAXN
+ MAXN
+ 10];
int a
[MAXN
+ 10], val
[MAXN
+ 10], size
[MAXN
+ 10], dp
[MAXN
+ 10][MAXN
+ 10], n
, k
;
inline void add(int x
, int y
, int i
){head
[i
].to
= y
, head
[i
].nx
= a
[x
]; a
[x
] = i
;}
inline int read(){
int x
= 0;
char c
= getchar();
while (!isdigit(c
))c
= getchar();
while (isdigit(c
))x
= (x
<< 1) + (x
<< 3) + (c
& 15), c
= getchar();
return x
;
}
void dfs(int x
, int fa
){
size
[x
] = 1;
for (register int i
= a
[x
]; i
; i
= head
[i
].nx
){
int v
= head
[i
].to
;
if (v
== fa
) continue;
for (register int j
= val
[x
]; j
<= k
; ++j
)
dp
[v
][val
[v
] + j
] = dp
[x
][j
] * P
% Mod
;
dfs(v
, x
); size
[x
] += size
[v
];
for (register int j
= val
[x
]; j
<= k
; ++j
)
dp
[x
][j
] = (dp
[x
][j
] * P
+ dp
[v
][j
]) % Mod
;
}
}
signed main(){
freopen
("luge.in", "r", stdin);
freopen
("luge.out", "w", stdout);
n
= read(), k
= read();
for (register int i
= 1; i
<= n
; ++i
) val
[i
] = read();
for (register int i
= 1; i
< n
; ++i
){
int x
= read(), y
= read();
add(x
, y
, i
+ i
- 1);
add(y
, x
, i
+ i
);
}
dp
[1][val
[1]] = 1;
dfs(1, 0);
cout
<< dp
[1][k
] << endl
;
return 0;
}
