在一个忍者的帮派里，一些忍者们被选中派遣给顾客，然后依据自己的工作获取报偿。
在这个帮派里，有一名忍者被称之为Master。除了Master以外，每名忍者都有且仅有一个上级。为保密，同时增强忍者们的领导力，所有与他们工作相关的指令总是由上级发送给他的直接下属，而不允许通过其他的方式发送。
现在你要招募一批忍者，并把它们派遣给顾客。你需要为每个被派遣的忍者支付一定的薪水，同时使得支付的薪水总额不超过你的预算。另外，为了发送指令，你需要选择一名忍者作为管理者，要求这个管理者可以向所有被派遣的忍者发送指令，在发送指令时，任何忍者（不管是否被派遣）都可以作为消息的传递人。管理者自己可以被派遣，也可以不被派遣。当然，如果管理者没有被排遣，你就不需要支付管理者的薪水。
你的目标是在预算内使顾客的满意度最大。这里定义顾客的满意度为派遣的忍者总数乘以管理者的领导力水平，其中每个忍者的领导力水平也是一定的。
写一个程序，给定每一个忍者i的上级Bi，薪水Ci，领导力Li，以及支付给忍者们的薪水总预算M，输出在预算内满足上述要求时顾客满意度的最大值。
第一行包含两个整数N和M，其中N表示忍者的个数，M表示薪水的总预算。
接下来N行描述忍者们的上级、薪水以及领导力。其中的第i行包含三个整数Bi,Ci,Li分别表示第i个忍者的上级，薪水以及领导力。Master满足Bi=0，并且每一个忍者的老板的编号一定小于自己的编号Bi<i。
输出一个数，表示在预算内顾客的满意度的最大值。
输入 #1复制
5 4 0 3 3 1 3 5 2 2 2 1 2 4 2 3 1输出 #1复制
61 ≤ N ≤ 100,000 忍者的个数；
1 ≤ M ≤ 1,000,000,000 薪水总预算；
0 ≤ Bi < i 忍者的上级的编号；
1 ≤ Ci ≤ M 忍者的薪水；
1 ≤ Li ≤ 1,000,000,000 忍者的领导力水平。
对于 30%的数据，N ≤ 3000。
题意:很简单给出一棵树， 一共n个点， 每个点两个属性a, b。
求某点X满足， 其子树中的某一个点集满足, 此时的收益为
点集大小 * X 的 b属性, 求最大收益。
做的时候以为当前点X不能算, WA到两眼发黑。
思路: 每一个节点存一个set, 对于其子节点的set, 用大的来合并小的。(貌似这就叫启发式合并)
此时的复杂度为
一共n个节点, 每个节点最坏合并情况, 每次合并后长度加倍，但元素总和不超过n个， 所以
均摊最多次插入, 每次插入复杂度, 所以总时间复杂度
#include <bits/stdc++.h> #include <unordered_map> using namespace std; typedef long long ll; typedef unsigned long long ull; #ifdef LOCAL #define debug(x) cout << "[" __FUNCTION__ ": " #x " = " << (x) << "]\n" #define TIME cout << "RuningTime: " << clock() << "ms\n", 0 #else #define TIME 0 #endif #define hash_ 1000000009 #define Continue(x) { x; continue; } #define Break(x) { x; break; } const int mod = 998244853; const int N = 1e6 + 10; const int INF = 0x3f3f3f3f; const ll LINF = 0x3f3f3f3f3f3f3f3f; ll fpow(ll a, ll b, ll mod) { ll res = 1; for (; b > 0; b >>= 1) { if (b & 1) res = res * a % mod; a = a * a % mod; } return res; } int a[N]; int b[N]; int he[N]; int MX; vector<int>G[N]; multiset<int>s[N]; ll ans; void dfs(int x) { if (a[x] <= MX) { he[x] = a[x]; s[x].insert(a[x]); } for (auto &i : G[x]) { dfs(i); if (s[i].size() > s[x].size()) swap(s[i], s[x]), swap(he[i], he[x]); for (auto & j : s[i]) { auto num = (--s[x].end()); if (he[x] + j <= MX) s[x].insert(j), he[x] += j; else { if (j <= *num) he[x] -= *num - j, s[x].erase(num), s[x].insert(j); else break; } } } ans = max(ans, (ll)s[x].size() * b[x]); } int main() { #ifdef LOCAL freopen("D:/input.txt", "r", stdin); #endif int n; scanf("%d%d", &n, &MX); int x, y, z; for (int i = 1; i <= n; i++) { scanf("%d%d%d", &x, &y, &z); G[x].push_back(i); a[i] = y; b[i] = z; } dfs(0); cout << ans << endl; return TIME; }
