【题目链接】 http://www.lydsy.com/JudgeOnline/problem.php?id&＃61;2809
【题目大意】
给出一棵树&＃xff0c;求出每个点有个权值&＃xff0c;和一个乘算值&＃xff0c;请选取一棵子树&＃xff0c;
并在这个子树上选择一些节点&＃xff0c;使得根节点的乘算值乘上选取的节点数价值最大&＃xff0c;
并且权值和不超过给定的限制
【题解】
我们在树上做dfs&＃xff0c;计算每个点作为子树根节点时候的价值&＃xff0c;
维护可并的权值大根堆&＃xff0c;自下而上合并&＃xff0c;当发现权值和大于限制的时候pop根节点即可。
【代码】
#include
#include
#include
using namespace std;
typedef long long LL;
const int N&＃61;100010;
int x,n,m,cnt,tot;
vector
LL ans,sum[N],size[N];
int C[N],L[N],root[N];
struct SHeap{int v[N],l[N],r[N];int merge(int x,int y){if(x&＃61;&＃61;0||y&＃61;&＃61;0)return x&＃43;y;if(v[x]
void dfs(int x){root[x]&＃61;&＃43;&＃43;tot; heap.v[tot]&＃61;C[x];size[x]&＃61;1; sum[x]&＃61;C[x];for(int i&＃61;0;i
}
int main(){scanf("%d%d",&n,&m);for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;){scanf("%d%d%d",&x,&C[i],&L[i]);v[x].push_back(i);}dfs(1);printf("%lld\n",ans);return 0;
}
京公网安备 11010802041100号