Advertisement
Guest User

LCA

a guest
Mar 23rd, 2019
84
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.25 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define endl "\n"
  5. #define ll long long
  6.  
  7. constexpr int N = 1e5+1, L = 18;
  8.  
  9. vector<int> dp[N], g[N];
  10. int tin[N], tout[N], a[2*N], t=0;
  11.  
  12. void dfs(int v, int p = 0)
  13. {
  14. tin[v]=++t;
  15. dp[v][0] = p;
  16. for (int i = 1; i < L; i++)
  17. {
  18. dp[v][i] = dp[dp[v][i-1]][i-1];
  19. }
  20. for(auto u:g[v])
  21. {
  22. if (u!=p)
  23. dfs(u, v);
  24. }
  25. tout[v]=++t;
  26. }
  27.  
  28. bool upper(int a, int b)
  29. {
  30. return (tin[a]<=tin[b]&&tout[a]>=tout[b]);
  31. }
  32.  
  33.  
  34. int lca(int a, int b)
  35. {
  36. if (upper(a, b)) return a;
  37. if (upper(b, a)) return b;
  38. for (int i = L-1; i >= 0; i--)
  39. {
  40. if(!upper(dp[a][i], b))
  41. a = dp[a][i];
  42. }
  43. return dp[a][0];
  44. }
  45.  
  46. void change_root(int r)
  47. {
  48.  
  49. }
  50.  
  51.  
  52. void Solve()
  53. {
  54. ll n, m, x, y, z, ans = 0, la = 0;
  55. cin >> n >> m;
  56. for (int i = 1; i < n; i++)
  57. {
  58. int par;
  59. cin >> par;
  60. g[par].push_back(i);
  61. }
  62. cin >> a[0] >> a[1] >> x >> y >> z;
  63. for (int i = 2; i < 2*m; i++)
  64. {
  65. a[i] = (x*a[i-2]+y*a[i-1]+z)%n;
  66. }
  67. dfs(0);
  68. for(int i = 1; i < 2*m; i+=2)
  69. {
  70. la = lca((a[i-1]+la)%n, a[i]);
  71. ans+=la;
  72. }
  73. cout << ans;
  74. return;
  75. }
  76.  
  77. int main() {
  78. std::ios_base::sync_with_stdio(false);
  79. std::cin.tie(nullptr);
  80. Solve();
  81. return 0;
  82. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement