Advertisement
Guest User

I

a guest
Sep 27th, 2020
392
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.12 KB | None | 0 0
  1. #include "bits/stdc++.h"
  2. // #pragma GCC optimize("Ofast")
  3. // #pragma GCC optimize ("unroll-loops")
  4. // #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  5. using namespace std;
  6. using ll = long long int;
  7. const int mod = 1e9+7;
  8. const int N = 5e4 + 5;
  9. int a[N], in[N], out[N], b[N], lst[N], dep[N];
  10. int T = 1;
  11. void dfs(vector<vector<int>> &g, int u, int v)
  12. {
  13.     in[u] = T++;
  14.     b[in[u]] = a[u];
  15.     if (v) dep[in[u]] = 1 + dep[in[v]];
  16.     for (auto x : g[u]) {
  17.         if (x == v) continue;
  18.         dfs(g, x, u);
  19.     }
  20.     out[u] = T;
  21. }
  22.  
  23. int main()
  24. {
  25.     // ios::sync_with_stdio(0); cin.tie(0);
  26.  
  27.     int n, q; cin >> n >> q;
  28.     for (int i = 1; i <= n; ++i) {
  29.         cin >> a[i];
  30.         lst[i] = -2*N;
  31.     }
  32.     vector<vector<int>> g(n+1);
  33.     for (int i = 2; i <= n; ++i) {
  34.         int par; cin >> par;
  35.         g[par].push_back(i);
  36.         g[i].push_back(par);
  37.     }
  38.     dfs(g, 1, 0);
  39.     for (int tm = 1; tm <= q; ++tm) {
  40.         int u; cin >> u;
  41.         int sm = 0, ct = 0;
  42.         for (int i = in[u]; i < out[u]; ++i) {
  43.             int mul = (lst[i]+b[i] <= tm);
  44.             sm += mul*(dep[i]-dep[in[u]]);
  45.             ct += mul;
  46.             lst[i] = mul ? tm : lst[i];
  47.         }
  48.         cout << sm << ' ' << ct << endl;
  49.     }
  50. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement