zcmimi's blog

arrow_back树形dp共11篇文章

avatar
zc
2020-10-21 16:41:02

查看原题

点击跳转

解法一

最小权覆盖集 = 全集 - 最大权独立集

动态dp

只要把强制取点,不取点可以分别把点的权值改为正无穷与负无穷

解法二

倍增/树链剖分+树形dp

每次修改的两个点a,b构成一条链

可以链上连接的子树与链中间的点的结果不受修改影响,只有a,b的转移受影响,需要单独处理

那么我们可以把子树的答案都预处理出来,链中间部分可以用倍增或树链剖分维护

这样只需要处理a,b

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

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

还有一点期望

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

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

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

分成两种情况:

  1. 直接通电 : q_i

  2. 被子节点通电 :

    (1-q_i) \times P_{to}(\text{子节点}) \times e_i.w(\text{连接的边导电的概率})

我们再考虑down(考虑子树外))

我们可以通过父节点的答案来更新子节点

父节点的答案是包括当前子节点的

可以把这部分除去然后按照up的方法更新

P_x= P_x' (1-P_x')*(P_{to}*e_i.w)(P_x'指根节点除去当前子节点的贡献的答案)

整理得: P_x'=\frac{P_x-(P_{to} \times e_i.w)}{1-(P_{to} \times e_i.w)}

(这里有个坑点:当1-(P_{to} \times e_i.w) = 0时这个式子就没有意义了)

\therefore P_{to} = P_{to} + (1-P_{to}) \times P_x' \times e_i.w

所以在下推的时候要特判一下

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

很裸的树形dp

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

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

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

f[i][j]=\max(lw+f[l][j-1],rw+f[r][j-1])

f[i][j]=\max(lw+f[l][k-1],rw+f[r][j-k-1])

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

树形dp up and down

考虑 up:

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

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

考虑 down:

s_{to} = s_{to} + (s_x-s_{to}-siz_{to}) + n - siz_{to}

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

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

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

解法1:

贪心

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

每次取出深度最大的点

从根结点往它父亲连边

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

解法2:

树形dp

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

思路剧毒无比

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

f[i][j] = \max(f[i][k] \times f[to][j-k])

f[i][0] = \max(f[i][0],f[i][j] \times j)

还没完

吐血的是还要写高精

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

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

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

无标题.png

设当前节点为x,路径有三种情况,上图分别对应情况1,情况2,情况3

  1. x子树内\rightarrow x \rightarrow x子树外(包括x)

  2. x子树内(包括x)\rightarrow x \rightarrow x子树内

  3. x子树外\rightarrow x \rightarrow x子树内

我们可以先处理出与x的距离为偶数和与x的距离为奇数的点的个数,分别记作f_x,g_x

那么f_x = 1 + \sum g_{to},g_x = 1 + \sum f_{to}(tox的孩子)

我们来考虑所有情况

  1. ans += V_x \times (f_x-g_x) \times (n-siz_x+1)(可以在x的子树中随机选一个往子树外面走(可以指走到x))

  2. ans += V_x \times (g_{to}-f_{to}) \times (siz_x-siz_{to}-1)

    ans+= V_x \times (siz_x-1)(可以从x直接向下走)

  3. 我们需要记录x子树外与x的距离为偶数和与x的距离为奇数的点的个数,分别记作uf_x,ug_x

    我们可以通过bfs从上到下来处理,那么

    uf_x=ug_{fa_x}+g_{fa_x}-f_x

    ug_x=uf_{fa_x}+f_{fa_x}-g_x

    ans += V_x \times (uf_x-ug_x) \times siz_x

接下来放代码:

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

树形dp 长链剖分

加强版

先来考虑1 \le n \le 5000

f[i][j]表示在i的子树中与i距离为j的点数

显然f[i][j] = \sum f[to][j-1](f[i][0] = 1)

g[i][j]表示以i为根的子树中,点对(x,y)满足x,ylca(x,y)距离都是d,并且lca(x,y)i的距离为d-j的点对数

g[i][j] = \sum g[to][j+1]

ans = \sum_{i=1}^n (g[i][0]+g[i][j] \times f[to][j-1])

我们来考虑加强版

n \le 100000

有点像静态链分治和树链剖分

我们计算长链的时候结果不需要清空,其他儿子节点重新计算

这样可以省下长链的时间

长链剖分真是个毒瘤(指针毒瘤)

1/2
Search
search