menu zcmimi's blog

arrow_back 树形dp

树形dp up and down

考虑 up:

s_x为点x子树中所有点到x的距离之和

S_x = \sum (s_{to}+siz_{to})

考虑 down:

zc
2019-12-21 19:47

树形dp 长链剖分

加强版

先来考虑1 \le n \le 5000

设$f

zc
2019-12-21 19:47

思路剧毒无比

f[i][j]表示在i的子树中,i所在的连体块大小为j\frac{\text{最大得分}}{j}

$f[i][j] = \max(f[i][k] \times

zc
2019-12-21 19:47

这篇题解可能是对楼下的补充

我们考虑每个点能贡献多少次

无标题.png

设当前节点为$

zc
2019-12-21 19:47

f_x表示在x放置且x的子树都被覆盖最少多少

g_x表示不在x放置且x的子树都被覆盖最少多少(x可以不被覆盖)

s_x表示在x放置且x的子树都被覆盖最

zc
2019-12-21 19:47

树形dp中的\text{up and down}

还有一点期望

设每个点能够通电的概率为P_i

那么ans = \sum_{i=1}^n P_i

**我们先考虑up(只考虑子树

zc
2019-12-21 19:47

tarjan找出强连通分量之后树形dp ```cpp

include<bits/stdc++.h>

namespace ZDY{

#pragma GCC optimize(3)
#d
zc
2019-12-21 19:47

解法1:

贪心

把深度大于2的都加到堆中

每次取出深度最大的点

从根结点往它父亲连边

然后把周围的节点标记为已经覆盖

解法2:

树形dp ```cpp

include<bi

zc
2019-12-21 19:47

```cpp

include

include

include

include

using namespace std; co

zc
2019-12-21 19:47

很裸的树形dp

因为是二叉树,所以处理起来非常方便

f[i][j]为根为i的子树用了j条边,最多保留多少,

l,r表示左右节点,lw,rw表示连接左右儿子的边的权值分别为多

zc
2019-12-21 19:47
1 / 1
Search
search