Advertisement
Guest User

Untitled

a guest
Feb 22nd, 2017
63
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.49 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define D 100007
  3. #define lg 25
  4.  
  5. using namespace std;
  6. typedef long long ll;
  7.  
  8. vector <ll> a[D];
  9. ll tin[D], tout[D], dp[D][lg + 1], za[2*D], timer, x, y, z, n, m;
  10.  
  11. void dfs();
  12. void questions();
  13. ll lca();
  14. bool upper();
  15.  
  16. bool upper(ll parent, ll v)
  17. {
  18. return (tin[parent] <= tin[v] && tout[v] <= tout[parent]);
  19. }
  20. void dfs(ll v, ll parent)
  21. {
  22. tin[v] = ++timer;
  23. dp[v][0] = parent;
  24. ll i, nn = a[v].size();
  25. for (i = 1; i < lg; i++)
  26. dp[v][i] = dp[dp[v][i - 1]][i - 1];
  27. for (i = 0; i < nn; i++)
  28. if (a[v][i] != parent)
  29. dfs(a[v][i], v);
  30. tout[v] = ++timer;
  31. }
  32. ll lca(ll a1, ll a2)
  33. {
  34. if (upper(a1, a2))
  35. return a1;
  36. if (upper(a2, a1))
  37. return a2;
  38.  
  39. for (ll i = lg - 1; i >= 0; i--)
  40. if (!upper(dp[a1][i], a2))
  41. a1 = dp[a1][i];
  42. return dp[a1][0];
  43. }
  44. void questions()
  45. {
  46. ll i;
  47. for (i = 3; i <= m + 3; i++)
  48. za[i] = (x*za[i - 2] + y*za[i - 1] + z) % n;
  49. ll res = 0;
  50. ll v = lca(za[1], za[2]);
  51. res += v;
  52. for (ll i = 2; i <= m; i++)
  53. {
  54. ll p1 = (za[2*i-1] + v) % n, p2 = za[2*i];
  55. v = lca(p1, p2);
  56. res += v;
  57. }
  58. cout << res << endl;
  59. }
  60.  
  61. int main()
  62. {
  63. ll i, v;
  64. cin >> n >> m;
  65. for (i = 0; i < n - 1; i++)
  66. {
  67. cin >> v;
  68. a[i].push_back(v);
  69. a[v].push_back(i);
  70. }
  71. cin >> za[1] >> za[2] >> x >> y >> z;
  72. dfs(0, 0);
  73. questions();
  74. return 0;
  75. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement