[TIOJ] 1429. [APIO '12] 忍者調度問題

題目連結:http://tioj.infor.org/problems/1429

---

本題其實有很多種寫法，例如：樹剖、整體二分搜、堆(啟發式合併或可合併)，我這裡的做法是用可合併堆的做法，也是裡面最快的一種(?，可以發現對於某個節點，如果已知他所有小孩的選法，那就把那些節點全部混在一起，然後如果超過預算就把最大的移掉，而因為要找最大的，我們需要用到heap，不過我們還需要快速合併多個堆，所以可以採用可合併堆，或是直接啟發式合併就好。
我在這裡採用的可合併堆是配對堆，雖然大家都寫左偏樹，不過我覺得配對堆比較好寫XDD，一種似乎均攤複雜度接近費波那契堆的東東，詳細證明可以看他的論文，不過我也不是很熟，簡單說一下他的做法:合併跟插入都是直接跟根比大小後決定誰當根，所以有可能一個根下面有一堆小孩，為了解決會因此爛掉的狀況，於使我們在pop的時候讓他的小孩們緊縮一點(?，就是pop時就把他的小孩兩兩合併，直到剩一個為止。似乎跟splay tree有點類似，大概這樣吧
註:這裡採用的合併方式因為有點懶人，根據論文他只能證出$O(\frac{log n log log n}{ log log log n})$的上界，不過$ \frac{ \frac{log n log log n}{ log log log n} }{log n}$在$n < 10^9$時只大約等於2而已

#include <bits/stdc++.h>
using namespace std;
#define PB push_back
typedef long long lld;

#define N 100000

struct pairingNode{
	int val;
	vector<pairingNode*> child;
};

class pairingHeap{
	private:
		pairingNode* root;
		int count;
	public:
		lld sum=0;
		pairingHeap(){root=NULL;count=0;}
		inline bool empty(){return count==0;}
		inline int top(){return root->val;}
		inline int size(){return count;}
		inline void push(lld a){
			sum+=a;
			count++;
			if(root==NULL){
				root = new pairingNode;
				root->val=a;
			}else{
				auto temp = new pairingNode;
				temp->val=a;
				if(root->val>=temp->val)
					root->child.PB(temp);
				else{
					temp->child.PB(root);
					swap(temp,root);
				}
			}
		}
		inline void join(pairingHeap& a){
			sum+=a.sum;
			count+=a.size();
			auto temp = a.root;
			if(root->val>=temp->val){
				root->child.PB(temp);
			}else{
				temp->child.PB(root);
				swap(temp,root);
			}
		}
		inline void pop(){
			sum-=root->val;
			count--;
			queue<pairingNode*> QQ;
			for(auto i:root->child) QQ.push(i);
			delete root;
			while(QQ.size()>1){
				pairingNode* tp1=QQ.front();QQ.pop();
				pairingNode* tp2=QQ.front();QQ.pop();
				if(tp1->val>tp2->val){
					tp1->child.PB(tp2);
					QQ.push(tp1);
				}else{
					tp2->child.PB(tp1);
					QQ.push(tp2);
				}
			}
			if(QQ.empty()) root=NULL;
			else root = QQ.front();
		}	
};

struct ninja{
	lld leader,cost;
	vector<int> child;
};

ninja people[N+5];
lld ans=0,maxCost;

void DFS(int,pairingHeap&);

int main(int argc, char* argv[]){
	int n,root;
	scanf("%d%lld",&n,&maxCost);
	for(int i=0;i<n;i++){
		int ll;
		scanf("%d%lld%lld",&ll,&people[i].cost,&people[i].leader);
		if(ll!=0) people[ll-1].child.PB(i);
		else root=i;
	}
	pairingHeap each;
	DFS(root,each);
	printf("%lld",ans);
	return 0;
}

void DFS(int w, pairingHeap& cur){
	cur.push(people[w].cost);
	for(auto i:people[w].child){
		pairingHeap each;
		DFS(i,each);
		cur.join(each);
	}
	while(cur.sum>maxCost) cur.pop();
	ans = max(ans, people[w].leader*cur.size());
}