题意:给定一棵树,问你最小删除多少个边,可以得到一个只函数k个节点的子树。

思路:d[i][j] 表示以i为根节点的子树中只存在j个节点的方法数。初始值 d[i][1] = sum[i] 表示以i为根节点的子树如果只存在一个节点,那么就是把所有的子节点都删掉。

然后后面访问的时候,如果使用了其中一个子节点,那么就要在状态里面减一。

最后扫一遍所有的节点,只要不是跟节点d[i][k] + 1,就是相当于把父节点与其连的边删掉。

 

 

HDU 3586 Information Disturbing (二分+树形dp)

题意:给定一棵树,删除一些边,问所有叶子节点不与根节点相连的这些边的权值之和小于等于m的情况下的边的权值的最大值的最小值是多少。 思路:二分这个最大...

阅读全文

Codeforces Round #322 (Div. 2) F. Zublicanes and Mumocrates(树形背包)

题意:给定一颗树,以不可能成为叶子的节点为根建树,把所有的节点分成两部分A,B。并且叶子节点各占一半,相邻的节点如果不同时属于一方,则删除,问最少删除...

阅读全文

HDU 4276 The Ghost Blows Light(树形dp,树上背包)

题意:给你一棵树,每条边上都有一个权值时间,每个节点也有一个权值。现在问你从1走到n,在规定的时间内,可以收获最大的权值是多少。 思路:最开始想这个题...

阅读全文

欢迎留言

*