fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. //
  4. const int maxn = 1e5 + 5;
  5. const int S = 320;
  6. //
  7. int n, q, a[maxn], p[maxn];
  8. int depth[maxn], cnt[maxn], orz[maxn];
  9. vector<int> adj[maxn];
  10. long long val[maxn][S];
  11. //
  12. void DFS (int u = 1, int d = 0)
  13. {
  14.     depth[u] = d;
  15.     orz[u] = cnt[d]++;
  16.     for (int v : adj[u])
  17.         DFS(v, d + 1);
  18. }
  19. long long query (int x, int y)
  20. {
  21.     if (x == 0 && y == 0)
  22.         return 0;
  23.     if (cnt[depth[x]] < S && val[x][orz[y]] != 0)
  24.         return val[x][orz[y]];
  25.     //
  26.     long long res = query(p[x], p[y]) + 1LL * a[x] * a[y];
  27.     //
  28.     if (cnt[depth[y]] < S)
  29.         val[x][orz[y]] = val[y][orz[x]] = res;
  30.     return res;
  31. }
  32. //
  33. void process (void)
  34. {
  35.     cin >> n >> q;
  36.     for (int i = 1; i <= n; ++i)
  37.         cin >> a[i];
  38.     for (int i = 2; i <= n; ++i)
  39.         cin >> p[i],
  40.         adj[p[i]].emplace_back(i);
  41.  
  42.     DFS();
  43.  
  44.     for (int x, y; q--; cout << '\n')
  45.         cin >> x >> y,
  46.         cout << query(x, y);
  47. }
  48. //
  49. signed main (void)
  50. {
  51.     ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  52.     process();
  53. }
Success #stdin #stdout 0s 7784KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/2r1pKA
https://m...content-available-to-author-only...j.com/problem/494
language:
C++14 (gcc 8.3)
created:
11 hours 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!