Description
有 \(n\) 条河和 \(m+1\) 个交汇处构成一棵以 \(0\) 号点（即大海） 为根的树。
每条河有各自的名称。对于一个交汇处，从它流出的干流的名称是流入这个交汇处的各个支流的名称之一。一条河流的长度是以它为名称的河流的长度之和。对于一个可能的命名方案，一条河流的排名等于长度大于它的河流数 \(+1\) 。
对于每条河，求出它在所有命名方案中，最小的排名。
\(n,m\leq 5\times 10^5\)。
Solution
先考虑对于每条河怎么 \(O(n)\) 求答案。
容易发现当前河一定要一冲到底，设长度为 \(L\)，那么就要要求其余长度 \(>L\) 的河流数量最少。
然后从下往上考虑每个点，有下面 2 种情况：
- 如果有儿子流过来是长的，那么当前点就流这个最长的。
- 如果儿子流过来全是短的，那么流里面最短的。
这样递归处理即可做到 \(O(n)\)。
考虑怎样一次求出所有的答案。
这里有个转化就是只要求出所有河流中 \(>L\) 的河流的最小数量，而不用考虑当前河是否要连到根。
因为如果一个最小数量的方案当前河没有连到根，那么把当前河到根的路径上全都连到当前河一定不会更劣。
然后从小到大枚举 \(L\)，这时候有 3 种情况：
- 有儿子流过来是长的。
- 儿子流过来全是短的，但最短的流完当前点到父亲的边后变长。
- 儿子流过来全是短的，但最短的流完当前点到父亲的边后还是短的。
容易发现答案就是 2 号点的数量\(+1\)，并且随着 \(L\) 的增大，部分 2 号点会变为 3 号点，1 号点可能会变成 2 或 3 号点。
设 \(f_i\) 表示将 \(i\) 从 2 变到 3 的最小长度。
那么只要用一个 pair 的优先队列维护所有 2 号点，其中 \(\{l,x\}\) 分别表示 \(x\) 需要从 2 变到 3 的最小长度和当前点的编号。
每次从队列中取出 \(l\) 最小的 \(x\)，然后不停跳父亲，如果这个祖先 \(y\) 的所有儿子都变 3 并且 \(f_y\leq L\) 说明 \(y\) 也是 3 号点，就继续跳，否则退出。
最后如果跳出来一个 \(y\)，使得他的所有儿子全是 3 并且 \(f_y>L\) 就说明他变成了个 2 号点，加到队列里即可。
如果要输出一个任意 \(L\) 的答案，就只要找到求出的所有答案中小于等于 \(L\) 的最大长度的答案即可。
时间复杂度：\(O(n\log n)\)。
Code
#include <bits/stdc++.h>
// #define int int64_t
const int kMaxN = 1e6 + 5;
const int64_t kInf = 1e18;
int n, m;
int fa[kMaxN], w[kMaxN], cnt[kMaxN];
int64_t sum[kMaxN], f[kMaxN];
std::string name[kMaxN];
std::vector<int> G[kMaxN];
std::map<int64_t, int> mp;
std::priority_queue<std::pair<int64_t, int>, std::vector<std::pair<int64_t, int>>, std::greater<std::pair<int64_t, int>>> q;
void dfs(int u) {
int64_t minn = kInf;
for (auto v : G[u]) {
sum[v] = sum[u] + w[v];
dfs(v);
minn = std::min(minn, f[v]);
++cnt[u];
}
if (minn == kInf) f[u] = w[u];
else f[u] = minn + w[u];
}
void dickdreamer() {
std::cin >> n >> m;
for (int i = m + 1; i <= m + n; ++i) {
std::cin >> name[i] >> fa[i] >> w[i];
G[fa[i]].emplace_back(i);
}
for (int i = 1; i <= m; ++i) {
std::cin >> fa[i] >> w[i];
G[fa[i]].emplace_back(i);
}
dfs(0);
for (int i = m + 1; i <= m + n; ++i)
q.emplace(f[i], i);
for (; !q.empty();) {
auto [L, u] = q.top();
q.pop();
--cnt[fa[u]];
for (u = fa[u]; u && !cnt[u]; u = fa[u]) {
if (L >= f[u]) {
--cnt[fa[u]];
} else {
q.emplace(f[u], u);
break;
}
}
mp[L] = q.size() + 1;
}
mp[kInf] = 0;
for (int i = m + 1; i <= m + n; ++i)
std::cout << name[i] << ' ' << prev(mp.upper_bound(sum[i]))->second << '\n';
}
int32_t main() {
#ifdef ORZXKR
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
int T = 1;
// std::cin >> T;
while (T--) dickdreamer();
// std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
return 0;
}