397 字
1 分钟
牛客周赛_Round_144_E题
题目链接：https://ac.nowcoder.com/acm/contest/134957/E
周日打了一下牛客周赛，感觉这题值得深入学习一下，于是打算复现写一篇博客。
这题我们首先要把题目的意思转换为数学的递推公式，我们需要一步步根据它给的样例推导公式。
我们先来看根节点，根节点需要的总水量就是整个树的水量之和，我们这里用了一个来记录该节点及其所有子树填满所需要的总水量。所以根节点的水量之和就是。然后我们看节点。我们注意到节点在上的节点高度要比高，所以如果想要填瓶的前提是
1.节点及其子树全部填满了。
2.瓶的水高度已经达到了。
我们把这样可以达到瓶的状态记作。（由此也可知为，因为瓶一开始就可以灌水）也就是。而对于，我们可以注意到，它是瓶瓶口高度最低的瓶，所以它不需要加上。它的公式是，同理我们很容易推导，，，，。而知道了能够向该瓶注水的水量之后我们再加上当前节点需要的总水量就是我们填满该节点需要的总水量了。
具体如何在代码中实现详细我都写在注释里了。
复现代码：
#include <bits/stdc++.h>
using namespace std;using ll = long long;#define endl '\n'#define mod 998244353typedef pair<ll, ll> pll;
ll a[200010]; //该该节点的高度ll fa[200010]; //值对应节点i的父节点ull w[200010]; //该节点对应的父节点的瓶口高度
void solved() { int n; cin >> n; for(int i = 1; i <= n;i++) cin >> a[i]; for(int i = 2; i <= n;i++) cin >> fa[i]; for(int i = 2; i <= n;i++) cin >> w[i];
vector<vector<pll>> child(n + 1); //该节点的子节点(对应父节点的瓶身高度，子节点下标) for(int i = 2; i <= n;i++){ child[fa[i]].emplace_back(w[i], i); }
vector<ll> cost(n + 1); //该节点及其子树填满的总水量(推导中的sum) for (int i = n; i >= 1;i--){ cost[i] = a[i]; for(auto& p : child[i]){ cost[i] += cost[p.second]; } }
vector<ll> sum_v(n + 1); //对应该节点的父节点下，更小瓶身高度的子节点产生的贡献。(推导base公式中sum_i + w_i的那部分) for(int i = 1; i <= n;i++){ //将该节点的子节点的瓶身高度按从小到大排序 sort(child[i].begin(), child[i].end());
ll cost_pre = 0; //cost的前缀和，用来计算cost的对该节点sum_v的前缀贡献 for (auto& p : child[i]){ ll w_v = p.first; ll v = p.second; sum_v[v] = w_v + cost_pre; cost_pre += cost[v]; } }
vector<ll> base(n + 1); //达到该节点前我们所需要的总水量 for (int i = 2; i <= n;i++){ base[i] = base[fa[i]] + sum_v[i]; }
//直接输出填满每个节点的所需要的总水量(ans) for(int i = 1; i <= n;i++){ cout << cost[i] + base[i] << " "; }}
int main() { ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr); int _ = 1; while(_--){ solved(); } return 0;}我自己推导时的草稿：
牛客周赛_Round_144_E题
https://mkrari.cn/posts/nowcoder_round_144/