Description
在一個忍者的幫派里，一些忍者們被選中派遣給顧客，然后依據自己的工作獲取報償。在這個幫派里，有一名忍者被稱之為 Master。除了 Master以外，每名忍者都有且僅有一個上級。為保密，同時增強忍者們的領導力，所有與他們工作相關的指令總是由上級發送給他的直接下屬，而不允許通過其他的方式發送。現在你要招募一批忍者，并把它們派遣給顧客。你需要為每個被派遣的忍者 支付一定的薪水，同時使得支付的薪水總額不超過你的預算。另外，為了發送指令，你需要選擇一名忍者作為管理者，要求這個管理者可以向所有被派遣的忍者 發送指令，在發送指令時，任何忍者（不管是否被派遣）都可以作為消息的傳遞 人。管理者自己可以被派遣，也可以不被派遣。當然，如果管理者沒有被排遣，就不需要支付管理者的薪水。你的目標是在預算內使顧客的滿意度最大。這里定義顧客的滿意度為派遣的忍者總數乘以管理者的領導力水平，其中每個忍者的領導力水平也是一定的。寫一個程序，給定每一個忍者 i的上級 Bi，薪水Ci，領導力L i，以及支付給忍者們的薪水總預算 M，輸出在預算內滿足上述要求時顧客滿意度的最大值。

1 ≤N ≤ 100,000 忍者的個數；
1 ≤M ≤ 1,000,000,000 薪水總預算；
0 ≤Bi < i 忍者的上級的編號；
1 ≤Ci ≤ M 忍者的薪水；
1 ≤Li ≤ 1,000,000,000 忍者的領導力水平。

Input
從標準輸入讀入數據。
第一行包含兩個整數 N和 M，其中 N表示忍者的個數，M表示薪水的總預算。
接下來 N行描述忍者們的上級、薪水以及領導力。其中的第 i 行包含三個整 Bi , C i , L i分別表示第i個忍者的上級，薪水以及領導力。Master滿足B i = 0，并且每一個忍者的老板的編號一定小于自己的編號 Bi < i。
Output
輸出一個數，表示在預算內顧客的滿意度的最大值。

Sample Input
5 4
0 3 3
1 3 5
2 2 2
1 2 4
2 3 1
Sample Output
6

HINT
如果我們選擇編號為 1的忍者作為管理者并且派遣第三個和第四個忍者，薪水總和為 4，沒有超過總預算 4。因為派遣了 2 個忍者并且管理者的領導力為3，用戶的滿意度為 2,是可以得到的用戶滿意度的最大值。

我們需要處理出每個節點的孩子中滿足條件的盡可能多的節點，但是我們如果從上往下遍歷處理的話顯然會超時O(n^2)。

所以我們需要從下往上進行處理，盡可能地利用以前的信息，所以不妨對每個節點使用一個優先隊列，將滿足條件的都放進去，如果工資已經高于能負擔的工資，就把工資最高的那個人去掉。然后將相鄰兩個節點進行合并。為了提高效率，我們應當先處理重孩子，再處理輕孩子。

可是這樣使用STL自帶的優先隊列復雜度還不夠優秀，我們可以針對這個問題實現我們自己的優先隊列，所用的數據結構就是左偏樹

左偏樹是一種二叉堆，這種堆可以合并出高度比較低的樹，具體就是通過節點x到沒有右子樹的節點y的距離來進行判斷，及時交換左右孩子，從而使得堆不會變得很長。

這樣的堆有利于再和其他的堆進行合并。

合并的時候：從上往下合并，不斷地把根節點更大的右兒子和另一個堆合并。（可以證明這樣的復雜度最優秀）

具體到這個問題中，我們用節點類型存儲每個節點的數據，可是每個節點的根節點卻不一定是他本身，在二叉堆構造過程中，原本的位置已經改變，為了記錄這種改變，我們用root數組記錄在左偏樹中該節點的父親節點。（在訪問到他為止左偏樹中的節點都是實際樹形關系中他的孩子和他本身）

當目前工資已經超過最大工資的時候，我們就刪去堆頂元素（貪心思想，堆頂的工資最高，刪去他最劃算）

借鑒了網上的代碼加上自己的思考，發現自己這樣寫雖然沒有什么錯誤，但是還是應該把用于記錄堆關系的和用于記錄樹關系的數據分開，混在一起導致容易理解錯誤。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<climits>
#include<algorithm>
#include<ctime>
#include<cstdlib>
#include<queue>
#include<set>
#include<map>
#include<cmath>
#define rep(i,x,n) for(register int i=x;i<=n;i++) using namespace std;typedef long long ll;
const int MAXN=1e5+5;
struct Node
{int cost; ll ctrl;int rson,lson,dis;
}Tree[MAXN];
int nex[MAXN];
int head[MAXN],num=0;
int N; ll M;
int root[MAXN],sz[MAXN]; ll sum[MAXN];
ll ans=0;int Merge(int x,int y)
{if(!x || !y) return x+y;if(Tree[x].cost<Tree[y].cost) swap(x,y);Tree[x].rson=Merge(Tree[x].rson,y);if(Tree[Tree[x].rson].dis> Tree[Tree[x].lson].dis) swap(Tree[x].rson,Tree[x].lson);Tree[x].dis=Tree[Tree[x].rson].dis+1;return x;
}void Delete(int& x)
{x=Merge(Tree[x].lson,Tree[x].rson);
}int dfs(int x)
{root[x]=x;sum[x]=Tree[x].cost; sz[x]=1;for(int i=head[x];i;i=nex[i]){dfs(i);root[x]=Merge(root[x],root[i]);sum[x]+=sum[i]; sz[x]+=sz[i];}while(sum[x]>M){sum[x]-=Tree[root[x]].cost;sz[x]--;Delete(root[x]);}ans=max(ans,sz[x]*Tree[x].ctrl);
}int main()
{scanf("%d%lld",&N,&M);int t; //int Master=-1;rep(i,1,N){scanf("%d",&t);//if(t==0) Master=i;nex[i]=head[t]; head[t]=i;scanf("%d%lld",&Tree[i].cost,&Tree[i].ctrl);}dfs(1);printf("%lld",ans);return 0;
}