这道题只要读懂题目一切好说.

给出nnn个点的一棵树,每一个点有一个费用vvv和一个领导力aaa,给出费用上限mmm.求下面这个式子的最大值ax∗∣S∣ ( S⊂x的子树, ∑iv[i]≤m )\large a_x*|S|\ (\ S\sub x的子树,\ \sum_{i}v[i]\le m\ )ax∗∣S∣ ( S⊂x的子树, i∑v[i]≤m )

然后就做一遍dfsdfsdfs,对于一个点维护子树内的所有数的大根堆,如果当前堆的和大于mmm,就把堆顶元素弹出知道小于等于mmm.那么这样一定是最优的,因为子树内每个点在贡献上平等,费用大的就要优先弹出.

然后每个点就把子树的堆合并起来就行了.这里用左偏树实现

CODE

#include <vector>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int MAXN = 100005;

typedef long long LL;

struct lt {

    int ls, rs, v, d, sz; LL sum;

}t[MAXN];

vector<int>e[MAXN];

int n, m; LL a[MAXN], ans;

inline void upd(int x) {

	if(t[t[x].ls].d < t[t[x].rs].d) swap(t[x].ls, t[x].rs);

	t[x].d = t[t[x].rs].d + 1;

	t[x].sz = t[t[x].ls].sz + t[t[x].rs].sz + 1;

	t[x].sum = t[t[x].ls].sum + t[t[x].rs].sum + t[x].v;

}

int merge(int x, int y) {

    if(!x || !y) return x + y;

    if(t[y].v > t[x].v) swap(x, y);

    t[x].rs = merge(t[x].rs, y);

    upd(x);

    return x;

}

inline int pop(int x) {

    int l = t[x].ls, r = t[x].rs;

    t[x].ls = t[x].rs = t[x].d = 0; t[x].sz = 1;

    return merge(l, r);

}

inline int dfs(int x, int ff) {

	int rt = x;

	t[x].d = 0; t[x].sz = 1, t[x].sum = t[x].v;

	for(int v, i = 0, siz = e[x].size(); i < siz; ++i)

		if((v=e[x][i]) != ff) rt = merge(rt, dfs(v, x));

	while(t[rt].sum > m) rt = pop(rt);

	ans = max(ans, a[x] * t[rt].sz);

	return rt;

}

int main () {

    t[0].d = -1; t[0].sz = t[0].sum = 0;

	scanf("%d%d", &n, &m);

	for(int i = 1, x; i <= n; ++i) {

		scanf("%d%d%lld", &x, &t[i].v, &a[i]);

		if(x) e[x].push_back(i);

	}

	dfs(1, 0);

	printf("%lld\n", ans);

}

巴特西

BZOJ 2809: [Apio2012]dispatching（可并堆左偏树板题）

CODE

最新文章

热门文章

巴特西

BZOJ 2809: [Apio2012]dispatching（可并堆 左偏树板题）

CODE

最新文章

热门文章

BZOJ 2809: [Apio2012]dispatching（可并堆左偏树板题）