zcmimi's blog

arrow_back树型dp共5篇文章

avatar
zc
2020-04-26 16:20:00
查看原题

点击跳转

两次dfs即可

第一次dfs:

计算出每个点的子树,包含这个点,答案最大是多少

显然S_x=v_x+\sum\limits_{y\in son_x} [S_y>0]S_y

(若x为黑点v_x=-1,否则v_x=1)

第二次dfs:

通过x的父亲的答案来计算出x的答案

如果x目前的答案>0,则从x的答案减去x目前的答案

如果这个结果>0,那么x的答案加上这个结果

感觉直接看代码可能更直观

avatar
zc
2020-02-14 00:06:00
查看原题

点击跳转

首先可以dfs处理出所有路径的重要度(路径两端子树大小乘积)

然后就是树型dp处理出每个点影响的范围的重要度总和

最后取最大值就可以了

f(dis,x)表示与x距离不超过dis的所有路径的重要度

f(1,x)=\sum val(edge)

f(k,x)=\sum f(k-1,to)-f(k-2,x)

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

点击跳转

二分最大值,然后树型dp

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

点击跳转

f[i][0/1]表示以i为根的子树在i节点放置或不放置最少需要多少个

f[i][1]=1 + \sum \min(f[to][0],f[to][1])

f[i][0]=\sum f[1][to]

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

点击跳转

1/1
Search
search