1、题目大意:给一棵树和M值,每个点有两个权值C和L,选x个点,这x个点的C值的和不能超过M,且这x个点如果都在某个子树内
定义满意度为x*这个子树的根的L值
2、分析:这是一道可并堆的题目,我们考虑每一个子树,我们想让其中的选的点尽量多但是C和却不超过M
我们只需取C值最小的,次小的,第三小的……直到不能选为止,这个不是很简单吗,不就是一个堆吗
不对,难道对于每一个子树都要建一个堆吗,那不是爆了吗,我们只需把这个子树的所有子节点所在的堆全都合并
还要再加上这个子树的根节点,这样就可以了
#include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> using namespace std; #define M 1000000 #define LL long long struct merge_heap{ int l[M], r[M], d[M], value[M]; void init(){ memset(l, 0, sizeof(r)); memset(r, 0, sizeof(r)); memset(d, 1, sizeof(d)); } int merge(int x, int y){ if(!x) return y; if(!y) return x; if(value[x] < value[y]) swap(x, y); r[x] = merge(r[x], y); if(d[l[x]] < d[r[x]]){ swap(l[x], r[x]); } d[x] = d[l[x]] + 1; return x; } } wt; int n, m; int C[M], L[M]; int head[M], Next[M], son[M], tot; int tree[M]; int sum[M], size[M]; LL ans = 0; void dfs(int x){ for(int i = head[x]; i != -1; i = Next[i]){ dfs(son[i]); sum[x] += sum[son[i]]; size[x] += size[son[i]]; tree[x] = wt.merge(tree[x], tree[son[i]]); while(sum[x] > m){ size[x] --; sum[x] -= wt.value[tree[x]]; tree[x] = wt.merge(wt.l[tree[x]], wt.r[tree[x]]); } } ans = max((LL)L[x] * (LL)size[x], ans); } int main(){ memset(head, -1, sizeof(head)); scanf("%d%d", &n, &m); for(int i = 1; i <= n; i ++){ int fa; scanf("%d%d%d", &fa, &C[i], &L[i]); wt.value[i] = C[i]; Next[++ tot] = head[fa]; head[fa] = tot; son[tot] = i; sum[i] = C[i]; size[i] = 1; } wt.init(); for(int i = 1; i <= n; i ++) tree[i] = i; dfs(0); printf("%lld\n", ans); return 0; }