fork download
copy 
  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
comments (?)
stdin
copy 
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
copy 
4
2
3
2
https://ideone.com/nSQoYn
language:
C++14 (gcc 8.3)
created:
8 years 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!