fork download
  1. //84104971101048411497 - Can you guess what does this mean?
  2. using namespace std;
  3. #include <bits/stdc++.h>
  4. #define mapii map<int, int>
  5. #define debug(a) cout << #a << ": " << a << endl
  6. #define debuga1(a, l, r) fto(i, l, r) cout << a[i] << " "; cout << endl
  7. #define fdto(i, r, l) for(int i = (r); i >= (l); --i)
  8. #define fto(i, l, r) for(int i = (l); i <= (r); ++i)
  9. #define ftoa(i, l, r, a) for(int i = (l); i <= (r); i += a)
  10. #define forit(it, var) for(__typeof(var.begin()) it = var.begin(); it != var.end(); it++)
  11. #define forrit(rit, var) for(__typeof(var.rbegin()) rit = var.rbegin(); rit != var.rend(); rit++)
  12. #define ii pair<int, int>
  13. #define iii pair<int, ii>
  14. #define ff first
  15. #define ss second
  16. #define mp make_pair
  17. #define pb push_back
  18. #define ll long long
  19. #define maxN 100005
  20. #define maxB 20
  21.  
  22. template <class T>
  23. T min(T a, T b, T c) {
  24. return min(a, min(b, c));
  25. }
  26.  
  27. template <class T>
  28. T max(T a, T b, T c) {
  29. return max(a, max(b, c));
  30. }
  31.  
  32. struct FenwickTree {
  33. vector<ll> t;
  34. int n;
  35. void init(int _n) {
  36. n = _n;
  37. t.resize(n+1);
  38. }
  39. int update(int p, int x) {
  40. for(int i = p; i <= n; i += i &(-i)) {
  41. t[i] += x;
  42. }
  43. }
  44. int query(int p) {
  45. ll ans = 0;
  46. for(int i = p; i >= 1; i -= i &(-i)) {
  47. ans += t[i];
  48. }
  49. return ans;
  50. }
  51. void print() {
  52. fto(i, 1, n) printf("%d ", t[i]);
  53. puts("");
  54. }
  55. };
  56.  
  57. int n, k, q, p[maxN], l[maxN], r[maxN], d[maxN], b[maxB][maxN], cnt;
  58. vector<int> ke[maxN];
  59. FenwickTree T;
  60.  
  61. int LCA(int u, int v) {
  62. if (d[u] < d[v]) swap(u, v);
  63. int t = d[u]-d[v];
  64. fto(i, 0, k) {
  65. if (t&(1<<i)) u = b[i][u];
  66. }
  67. fdto(i, k, 0) {
  68. if (b[i][u] != b[i][v]) {
  69. u = b[i][u];
  70. v = b[i][v];
  71. }
  72. }
  73. if (u == v) return u;
  74. fto(i, 0, k) {
  75. if (b[i][u] == b[i][v]) return b[i][u];
  76. }
  77. }
  78.  
  79. void DFS(int u) {
  80. l[u] = ++cnt;
  81. forit(it, ke[u]) {
  82. int v = *it;
  83. if (v != p[u]) {
  84. d[v] = d[u]+1;
  85. DFS(v);
  86. }
  87. }
  88. r[u] = cnt;
  89. }
  90.  
  91. int main () {
  92. scanf("%d", &n);
  93. fto(i, 2, n) {
  94. scanf("%d", &p[i]);
  95. ke[i].pb(p[i]);
  96. ke[p[i]].pb(i);
  97. }
  98.  
  99. DFS(1);
  100. int k = (int)log2(n);
  101. fto(u, 1, n) b[0][u] = p[u];
  102. fto(i, 1, k) {
  103. fto(u, 1, n) b[i][u] = b[i-1][b[i-1][u]];
  104. }
  105.  
  106. T.init(n);
  107. fto(i, 1, n) {
  108. T.update(l[i], d[i]);
  109. T.update(l[i]+1, -d[i]);
  110. }
  111.  
  112. scanf("%d", &q);
  113. fto(i, 1, q) {
  114. int t, u, v;
  115. scanf("%d", &t);
  116. if (t == 1) {
  117. scanf("%d%d", &u, &v);
  118. int a = LCA(u, v);
  119. printf("%d\n", T.query(l[u])+T.query(l[v])-2*T.query(l[a]));
  120. }
  121. else {
  122. scanf("%d", &u);
  123. T.update(l[u], -1);
  124. T.update(r[u]+1, 1);
  125. }
  126. }
  127.  
  128. return 0;
  129. }
  130.  
Success #stdin #stdout 0s 14016KB
stdin
8
1 5 2 1 2 5 5
7
2 4
1 7 6
2 5
1 3 8
1 8 6
2 2
1 8 6
stdout
4
2
3
2