Guest User

LCA

a guest
Oct 20th, 2015
414
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.27 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <string>
  4. #include <vector>
  5. #include <queue>
  6. #include <stack>
  7. #include <set>
  8. #include <map>
  9. #include <deque>
  10. #include <list>
  11. #include <iterator>
  12. #include <functional>
  13. #include <sstream>
  14. #include <cstdio>
  15. #include <cstdlib>
  16. #include <cstring>
  17. #include <cctype>
  18. #include <cmath>
  19. #include <climits>
  20. #include <ctime>
  21. #include <cassert>
  22.  
  23. using namespace std;
  24.  
  25.  
  26. typedef long long ll;
  27. typedef long  double ld;
  28. typedef pair<double, double> pii;
  29. typedef pair<ll, ll> pll;
  30. typedef pair<ld, ld> pld;
  31. typedef pair<short, short> pss;
  32. #define fi first
  33. #define se second
  34. #define mp make_pair
  35. #define pb push_back
  36.  
  37.  
  38.  
  39. /////// begin
  40. const int MAXN = 200 * 1000;
  41. vector <int> g[MAXN];
  42. int tin[MAXN], tout[MAXN], pr[20][MAXN];
  43. bool was[MAXN];
  44. int t = 0;
  45.  
  46. void dfs(int v, int _pr){
  47.     if (was[v]) return;
  48.     was[v] = 1;
  49.     tin[v] = t++;
  50.     pr[0][v] = _pr;
  51.     for (int u: g[v])
  52.         dfs(u, v);
  53.     tout[v] = t++;
  54. }
  55.  
  56. bool is_pr(int v, int u){
  57.     return (tin[v] >= tin[u] && tout[v] <= tout[u]);
  58. }
  59.  
  60. int get_lca(int u, int v){
  61.     if (is_pr(u, v)) return v;
  62.     for (int i = 19; i >= 0; i--){
  63.         if (!is_pr(u, pr[i][v]))
  64.             v = pr[i][v];
  65.     }
  66.     return pr[0][v];
  67. }
  68.  
  69. int main() {
  70. #ifdef HOME
  71.     assert(freopen("input.txt", "r", stdin));
  72.     assert(freopen("output.txt", "w", stdout));
  73. #else
  74.   //freopen(FILE ".in", "r", stdin);
  75.   //freopen(FILE ".out", "w", stdout);
  76. #endif
  77.     //ios_base::sync_with_stdio(false);
  78.     //cin.tie(0);
  79.     int n, m;
  80.     cin >> n >> m;
  81.     for (int i = 1; i < n; i ++){
  82.         int a;
  83.         cin >> a;
  84.         g[a].pb(i);
  85.         g[i].pb(a);
  86.     }
  87.     memset(was, 0, sizeof was);
  88.     dfs(0, 0);
  89.     for (int i = 1; i < 20; i++)
  90.         for (int j = 0; j < n; j++){
  91.             pr[i][j] = pr[i - 1][pr[i - 1][j]];
  92.         }
  93.  
  94.  
  95.    
  96.     int a1, a2;
  97.     ll x, y, z;
  98.     int la = 0;
  99.     ll ans = 0;
  100.     cin >> a1 >> a2 >> x >> y >> z;
  101.     for (int i = 0; i < m; i++){
  102.         //cout << (a1 + la) % n << " " << a2 << endl;
  103.         la = get_lca((a1 + la) % n, a2) ;
  104.         ans += la;
  105.         a1 = (int)((a1 * x + a2 * y + z) % n);
  106.         a2 = (int)((a2 * x + a1 * y + z) % n);
  107.     }
  108.     cout << ans << endl;
  109.    
  110.     return 0;
  111. }
  112.  
  113. // end
Advertisement
Add Comment
Please, Sign In to add comment