BZOJ 2809: [Apio2012]dispatching

題目位址：http://www.lydsy.com/JudgeOnline/problem.php?id=2809

題目大意：在一棵樹中，每個節點有2個權值（val1和val2）。求一個節點x，在這個節點和其子樹中找一個點集S，使得Σval1(i),i∈S小于某個下界，并使得val2(x)*|s|最大。

算法分析：

        根據題目大意我們可以比較顯然的發現，在一個子樹中我們不斷地删除這個子樹的Max，我們總能使該子樹的sum小于下界，于是我們可以用堆來維護這個子樹的Max。因為如果某個節點對于該子樹不符合條件，那麼把它合并到規模更大的子樹中肯定更劣而不會更優。

        由于題目中嚴格保證了0<=Bi<i，我們隻需要從後往前将節點掃一遍，先維護這棵子樹的sum小于下界，再把它并到它父親所在的堆就可以了。

        對于一棵子樹val1的總和以及它的size，我們可以用類似線段樹Update操作進行維護。

        值得提醒的是，題目中給的val2的範圍已經達到了[1,1e9]，而點的個數的範圍又是[1,1e5]，是以我們需要用long long來記錄答案。

Code：

/*
 * Problem:2809
 * Author:PYC
 */

#include <cstdio>
#include <algorithm>

#define maxn 1000000

using namespace std;

int n,m,B[maxn],L[maxn],rt[maxn];
long long ans,t;

struct node{
	int key,l,r,num;
	long long sum;
}heap[maxn];

void up(int x){
	heap[x].sum=(long long)(heap[heap[x].l].sum+heap[heap[x].r].sum+(long long)heap[x].key);
	heap[x].num=heap[heap[x].l].num+heap[heap[x].r].num+1;
}

int merge(int p,int q){
	if (!p || !q) return p?p:q;
	if (heap[p].key<heap[q].key) swap(p,q);
	heap[p].r=merge(heap[p].r,q);
	up(p);
	swap(heap[p].l,heap[p].r);
	return p;
}

void del(int &x){
	x=merge(heap[x].l,heap[x].r);
}

void renew(int x){
	heap[x].l=heap[x].r=0;
}

int main(){
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;++i) scanf("%d%d%d",&B[i],&heap[i].key,&L[i]),rt[i]=i,heap[i].num=1,heap[i].sum=(long long)heap[i].key;
	for (int i=n;i;--i){
		while (heap[rt[i]].sum>(long long)m) del(rt[i]);
		if ((t=(long long)((long long)heap[rt[i]].num*(long long)L[i]))>ans) ans=t;
		if (rt[i] && B[i]) rt[B[i]]=merge(rt[B[i]],rt[i]);
	}
	printf("%lld\n",ans);
	return 0;
}
           

By Charlie Pan

Mar 9,2014