Brief description:
。。给定一颗 N 个节点的树，总资金 M。。。对每个节点有两个参数 C_u（代价）, L_u（收益因子）。。
。。对于一颗以 u 为根的子树。。你可以选择一组点集 S。。使得点集的代价和不超过 M。。则带来的收益是 L_u |S|。。
。。最大化收益。。。
Analysis:
…
算法一：平衡树启发式合并
。。贪心，对于每个点为根的子树，我们需要知道其子树中，前 k 小的结点分别是多少。。
那么最普通的做法是平衡树启发式合并。。
https://gist.github.com/lychees/ed2b51f66fa60305ac8d
算法二：暴力 + 路径压缩
然后这个题有一种很碉堡的暴力算法。。用路径压缩优化。。
（虽然最坏情况下还是会退化成 O(n2)。 m 特别大。。使得路径压缩不会发生。。。。但是居然可以 AC？）
（路径压缩。。3400ms+
/}/* .................................................................................................................................. */
const int N = int(1e5) + 9;
int p[N], c[N], l[N], o[N], s[N]; LL f[N];
int n; LL m, ans;
void gao(int x){
int r = c[x];
while (x){
if (r + f[x] <= m) f[x] += r, ++s[x];
else p[x] = p[p[x]];
x = p[x];
}
}
bool cmp(int a, int b){
return c[a] < c[b];
}
int main(){
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
#endif
RD(n, m); REP_1(i, n) RD(p[i], c[i], l[i]), o[i] = i;
sort(o+1, o+1+n, cmp); REP_1(i, n) gao(o[i]);
REP_1(i, n) checkMax(ans, (LL) l[i] * s[i]);
OT(ans);
}
算法三：左偏树？
http://www.cnblogs.com/jianglangcaijin/p/3458158.html
算法四：主席树
http://hi.baidu.com/greencloud/item/a0f0903b2148bfcb2e8ec2d3
