经验总结

  1. 首页 > 生活 > >

Codeforces Global Round 23 A-D( 二 )

生活百科


最后输出 \(f[1][0]\)，根节点没有多一条路径的选择 。
时间复杂度 \(O(n \log n)\)
空间复杂度 \(O(n)\)
代码#include <bits/stdc++.h>#define ll long longusing namespace std;vector<int> g[200007];int s[200007];ll f[200007][2];void dfs(int u, int p) {f[u][0] = 1LL * p * s[u];f[u][1] = f[u][0] + s[u];if (!g[u].size()) return;vector<ll> tb;for (auto v : g[u]) {dfs(v, p / g[u].size());f[u][0] += f[v][0];f[u][1] += f[v][0];tb.push_back(f[v][1] - f[v][0]);}sort(tb.begin(), tb.end(), [&](ll a, ll b) {return a > b;});int r = p % g[u].size();for (int i = 0;i < r;i++) f[u][0] += tb[i];for (int i = 0;i <= r;i++) f[u][1] += tb[i];}bool solve() {int n, k;cin >> n >> k;for (int i = 1;i <= n;i++) g[i].clear();for (int i = 2;i <= n;i++) {int p;cin >> p;g[p].push_back(i);}for (int i = 1;i <= n;i++) cin >> s[i];dfs(1, k);cout << f[1][0] << '\n';return true;}int main() {std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int t = 1;cin >> t;while (t--) {if (!solve()) cout << -1 << '\n';}return 0;}

经验总结扩展阅读


上一篇：学习ASP.NET Core Blazor编程系列九——服务器端校验

下一篇：私汤可以裸泡吗