https://codeforces.com/contest/1997/problem/D
题目大意
给以棵 $1$ 为根的有根树，节点数 $n \ (2 \le n \le 2 \times 10^5)$。每个节点上有权重 $a_i \ (1 \le a_i \le 10^9)$。每次操作可以选择给节点 $i$ 的权值 $+1$ 给其子树中所有其他节点权值 $-1$。任意时刻结点权值不能为负数，问经过操作根最大是多少。
简要题解
注意根只会变大不会变小，叶子只会变小不会变大。所以增加的上界就是最小的叶子的大小。 我们考虑根上增加的值，我们可以把所有对根的操作最后做（某次操作提前做没有意义，相当于提前给所有子树 $-1$，如果这是成立的话，那么后做显然子树状态也都是成立的）。如果能加 $k$ 则一定有一个时刻是加到 $k - 1$。则我们考虑二分这个 $k$。
考虑判断能不能增加 $k$。如果可以，相当于，对于一颗子树而言，最终一定是尽量“平均”。容易发现我们总是先做子树中的操作更好，因为先做父节点后做子树，那么 $+1$ 的影响不会传递上去就没有意义。考虑一颗子树，比 $k$ 多出来的部分是可以用来 $-1$ 去增加父节点的。当然如果某个节点包括其子树的贡献都无法达到 $k$ 的话，那么证明根增加 $k$ 是不可行的。
这个影响上传的过程有些细节需要注意：
-
叶子，直接和 $k$ 比较即可
-
非叶子，最小的子树贡献为 $x$：
a. $a[i] <= k$：这时需要叶子的贡献先补到 $k$，之后叶子的贡献 $/ 2$ 上传。（因为每次需要再消耗 $1$ 的贡献将当前子树的根变大，才能把整棵子树 $-1$ 再向上贡献）
b. $a[i] > k$：节点自己也可以向上贡献一些值，但注意如果 $a[i] - k > x$ 也只能向上贡献 $x$。其他情况可以贡献 $(a[i] - k + x) / 2$
复杂度
$T$：$O(n \log(max(a_i)))$
$S$：$O(n)$
代码实现
#include <bits/stdc++.h>
using namespace std;
int io_=[](){ ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();
using LL = long long;
using ULL = unsigned long long;
using LD = long double;
using PII = pair<int, int>;
using VI = vector<int>;
using MII = map<int, int>;
template<typename T> void cmin(T &x,const T &y) { if(y<x) x=y; }
template<typename T> void cmax(T &x,const T &y) { if(x<y) x=y; }
template<typename T> bool ckmin(T &x,const T &y) {
return y<x ? (x=y, true) : false; }
template<typename T> bool ckmax(T &x,const T &y) {
return x<y ? (x=y, true) : false; }
template<typename T> void cmin(T &x,T &y,const T &z) {// x<=y<=z
if(z<x) { y=x; x=z; } else if(z<y) y=z; }
template<typename T> void cmax(T &x,T &y,const T &z) {// x>=y>=z
if(x<z) { y=x; x=z; } else if(y<z) y=z; }
// mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
// mt19937_64 rnd_64(chrono::system_clock::now().time_since_epoch().count());
template<typename Func> struct YCombinatorResult {
Func func;
template<typename T>
explicit YCombinatorResult(T &&func) : func(std::forward<T>(func)) {}
template<class ...Args> decltype(auto) operator()(Args &&...args) {
return func(std::ref(*this), std::forward<Args>(args)...);
}
};
template<typename Func> decltype(auto) y_comb(Func &&fun) {
return YCombinatorResult<std::decay_t<Func>>(std::forward<Func>(fun));
}
/*
---------1---------2---------3---------4---------5---------6---------7---------
1234567890123456789012345678901234567890123456789012345678901234567890123456789
*/
const int INF = 0x3f3f3f3f;
void solve() {
int n; cin >> n;
vector<int> a(n);
for (int& i : a) cin >> i;
vector<vector<int>> g(n);
int p;
for (int i = 1; i < n; i++) {
cin >> p; p--;
g[p].push_back(i);
}
auto dfs = y_comb([&](auto dfs, int u, int tar) -> int {
int mn = INF;
for (int v : g[u]) {
cmin(mn, dfs(v, tar));
if (mn == -1) return -1;
}
if (mn == INF) {
return max(-1, a[u] - tar);
}
if (a[u] + mn < tar) return -1;
if (a[u] <= tar) {
mn -= tar - a[u];
return mn / 2;
} else { // a[u] > tar
if (a[u] - tar >= mn) {
return mn;
} else {
return (a[u] - tar + mn) / 2;
}
}
});
auto check = [&](int mid) -> bool {
int mn = INF;
for (int v : g[0]) {
cmin(mn, dfs(v, mid));
}
return mn >= 0;
};
int l = 1, r = 1e9;
int mid, ans = 0;
while (l <= r) {
mid = (l + r) >> 1;
if (check(mid)) {
ans = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
cout << ans + a[0] << '\n';
}
int main() {
int t = 1;
cin >> t;
while (t--) {
solve();
}
return 0;
}
Next: E. Level Up - Educational Codeforces Round 168