fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #pragma GCC optimize("O3")
  4. #pragma GCC optimize("O1")
  5. #pragma GCC optimize("O1")
  6. #pragma GCC optimize("unroll-loops")
  7. #pragma GCC optimize(3)
  8. #pragma GCC optimize("Ofast")
  9. #pragma GCC optimize("inline")
  10. #pragma GCC optimize("-fgcse")
  11. #pragma GCC optimize("-fgcse-lm")
  12. #pragma GCC optimize("-fipa-sra")
  13. #pragma GCC optimize("-ftree-pre")
  14. #pragma GCC optimize("-ftree-vrp")
  15. #pragma GCC optimize("-fpeephole2")
  16. #pragma GCC optimize("-ffast-math")
  17. #pragma GCC optimize("-fsched-spec")
  18. #pragma GCC optimize("-falign-jumps")
  19. #pragma GCC optimize("-falign-loops")
  20. #pragma GCC optimize("-falign-labels")
  21. #pragma GCC optimize("-fdevirtualize")
  22. #pragma GCC optimize("-fcaller-saves")
  23. #pragma GCC optimize("-fcrossjumping")
  24. #pragma GCC optimize("-fthread-jumps")
  25. #pragma GCC optimize("-freorder-blocks")
  26. #pragma GCC optimize("-fschedule-insns")
  27. #pragma GCC optimize("inline-functions")
  28. #pragma GCC optimize("-ftree-tail-merge")
  29. #pragma GCC optimize("-fschedule-insns2")
  30. #pragma GCC optimize("-fstrict-aliasing")
  31. #pragma GCC optimize("-falign-functions")
  32. #pragma GCC optimize("-fcse-follow-jumps")
  33. #pragma GCC optimize("-fsched-interblock")
  34. #pragma GCC optimize("-fpartial-inlining")
  35. #pragma GCC optimize("no-stack-protector")
  36. #pragma GCC optimize("-freorder-functions")
  37. #pragma GCC optimize("-findirect-inlining")
  38. #pragma GCC optimize("-fhoist-adjacent-loads")
  39. #pragma GCC optimize("-frerun-cse-after-loop")
  40. #pragma GCC optimize("inline-small-functions")
  41. #pragma GCC optimize("-finline-small-functions")
  42. #pragma GCC optimize("-ftree-switch-conversion")
  43. #pragma GCC optimize("-foptimize-sibling-calls")
  44. #pragma GCC optimize("-fexpensive-optimizations")
  45. #pragma GCC optimize("inline-functions-called-once")
  46. #pragma GCC optimize("-fdelete-null-pointer-checks")
  47. #define int long long
  48. #define cint const int
  49. #define ii pair<int, int>
  50. #define fi first
  51. #define se second
  52. #define vi vector<int>
  53. #define vii vector<vi>
  54. #define pb push_back
  55. #define pq priority_queue
  56. #define mid(l, r) ((l + r) >> 1)
  57. #define left(id) (id << 1)
  58. #define right(id) (id << 1  1)
  59. #define cntbit(mask) __builtin_popcountll(mask)
  60. #define BIT(mask, i) (mask & (1ll << (i)))
  61. #define ONBIT(mask, i) (mask | (1ll << (i)))
  62.  
  63. const int MAXN = 1015;
  64. const int MOD  = 1e9 + 7;
  65.  
  66. int N, Q;
  67. vector<int> g[MAXN];
  68. int d[MAXN];
  69. int par[MAXN], ans[MAXN], dp[MAXN];
  70.  
  71. void DFS(int u, int p) {
  72.     vector<int> tmp;
  73.     for (auto v : g[u]) {
  74.         if (v == p) continue;
  75.         DFS(v, u);
  76.         tmp.pb(d[v] + dp[v]);
  77.         dp[u] = max(dp[u], dp[v] + d[v]);
  78.     }
  79.     if (tmp.size() == 0) ans[u] = 0;
  80.     if (tmp.size() == 1) ans[u] = tmp[0];
  81.     if (tmp.size() >= 2) {
  82.         sort(tmp.begin(), tmp.end(), greater<int>());
  83.         ans[u] = tmp[0] + tmp[1];
  84.         ans[u] %= MOD;
  85.     }
  86. }
  87.  
  88.  
  89. signed main() {
  90.     ios_base::sync_with_stdio(0);
  91.     cin.tie(0);
  92.     cout.tie(0);
  93.  
  94.     cin >> N;
  95.     for (int i = 1; i < N; i++) {
  96.         int u;
  97.         cin >> u;
  98.         par[i] = u;
  99.         g[i].pb(u);
  100.         g[u].pb(i);
  101.     }
  102.  
  103.     for (int i = 1; i < N; i++) {
  104.         int dd;
  105.         cin >> dd;
  106.         d[i] = dd;
  107.     }
  108.     DFS(0, -1);
  109.     int res = 0;
  110.     for (int i = 0; i <= N - 1; i++) {
  111.         res += ans[i];
  112.         res %= MOD;
  113.     }
  114.     cout << res << '\n';
  115.     cin >> Q;
  116.     for (int i = 1; i <= Q; i++) {
  117.         for (int j = 0; j < N; j++) ans[j] = 0;
  118.         int u, add;
  119.         cin >> u >> add;
  120.         d[u] += add;
  121.         DFS(0, -1);
  122.         int res = 0;
  123.         for (int j = 0; j < N; j++) {
  124.             res += ans[j];
  125.             res %= MOD;
  126.         }
  127.         cout << res << '\n';
  128.     }
  129. }
  130.  
Success #stdin #stdout 0.01s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/hHXSiX
language:
C++14 (gcc 8.3)
created:
4 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!