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

思路:二分这个最大的边,然后去dp一下这个边是否满足题意即可。

d[i] 表示 以i 为根节点的子树中叶子节点都不与根节点i相连的最小权值是多少。

然后枚举i相连的边删不删的问题了。

 

POJ 1947 Rebuilding Roads (树形背包)

题意:给定一棵树,问你最小删除多少个边,可以得到一个只函数k个节点的子树。 思路:d[i][j] 表示以i为根节点的子树中只存在j个节点的方法数。初始值 d[i][1...

阅读全文

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

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

阅读全文

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

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

阅读全文

欢迎留言

*