长链剖分求 k 级祖先

前置知识

大概学过重链剖分吧。

重链剖分是重儿子，即 sz 最大的儿子，这个剖分是指长儿子，即 dep 最大的儿子。

这样子可以把树剖成一条一条链。比如下面这个图绿色的部分就是长链。

1. 一个节点到它所在的长链的链底部的路径，为从这个节点到它子树每个子树所有节点的路径中，最长的一条。
2. 一个节点到根的路径，最多经过 个虚边（这个我不太会算，大概就是这么构造一个树，每个从任何一个节点出发，每个结点到叶子节点的距离都是一样的同时在一个非叶子节点的儿子中，只有一个儿子结点可以有多个儿子，且如果这个结点的父亲结点有且仅有他一个儿子，那么这个结点也有且仅有一个儿子。就是一棵删减的完全二叉树。

应用例子

求 k 级祖先

对于每一条长链，记它的长度是 ，不妨从链顶向上记录 个结点，同时树上倍增。这样子，对于每个询问，我们向上跳 个结点，那么，这个结点的所处的链一定长度 ，而剩余的 个长度，我们可以先跳到链顶，然后判断是链顶向上还是向下即可。

#include <bits/stdc++.h>

#define gc( ) std::getchar( )
#define pc( i ) std::putchar( i )
#define space ' '
#define enter '\n'
#define RE cout << "Passing [" << __FUNCTION__ << "] on " << __LINE__ << enter
#define DEBUG(...) for( auto &i: __VA_ARGS__ ) cout << i << " "; cout << enter
using std::make_pair;

template < typename T >
inline T read( )
{
 T x = 0;
 char ch = gc( );
 bool f = 0;
 while( !std::isdigit( ch ) )
 {
  f = ( ch == '-' );
  ch = gc( );
 }
 while( std::isdigit( ch ) )
 {
  x = x * 10 + ( ch - '0' );
  ch = gc( );
 }
 return f ? -x : x;
}

template < typename T >
void print( T x )
{
 if( x < 0 )
 {
  x = -x;
  pc( '-' );
 }
 if( x < 10 )
 {
  pc( x + 48 );
  return;
 }
 print < T > ( x / 10 );
 pc( x % 10 + 48 );
 return ;
}

namespace Solution
{
#define IOS std::ios::sync_with_stdio( false ), std::cin.tie( 0 ), std::cout.tie( 0 )
#define Rep( i, j, k ) for( int i = j; i >= k; --i )
#define rdi( ) read < int > ( )
#define rdl( ) read < long long > ( )
#define pti( i ) print < int > ( i ), putchar( space )
#define ptl( i ) print < long long > ( i ), putchar( space )
#define For( i, j, k ) for( int i = j; i <= k; ++i )
 using std::cin;
 using std::cout;
 using std::endl;
 using std::vector;
 using std::map;
 using std::queue;
 using std::deque;
 using std::set;
 using std::pair;
#ifdef ONLINE_JUDGE
 const int N = 504001, mod = 1e9 + 7;
#else
 const int N = 10;
#endif
 int n, q, rt, g[ N ], fa[ N ][ 20 ], dep[ N ], son[ N ], d[ N ], top[ N ];
 vector < int > v[ N ], up[ N ], down[ N ];
 unsigned int s;
 void Dfs( int u )
 {
  dep[ u ] = d[ u ] = dep[ fa[ u ][ 0 ] ] + 1;
  for( auto &i: v[ u ] )
  {
   for( int j = 0; fa[ i ][ j ]; ++j )
    fa[ i ][ j + 1 ] = fa[ fa[ i ][ j ] ][ j ];
   Dfs( i );
   if( d[ i ] > d[ u ] )
    son[ u ] = i, d[ u ] = d[ i ];
  }
  return;
 }
 void Dfs( int u, int tp )
 {
  top[ u ] = tp;
  if( tp == u )
  {
   for( int i = 0, o = u; i <= d[ u ] - dep[ u ]; ++i )
    up[ u ].push_back( o ), o = fa[ o ][ 0 ];
   for( int i = 0, o = u; i <= d[ u ] - dep[ u ]; ++i )
    down[ u ].push_back( o ), o = son[ o ]; 
  }
  if( son[ u ] )
   Dfs( son[ u ], tp );
  for( auto &i: v[ u ] ) if( i != son[ u ] )
   Dfs( i, i );
  return;
 }
 inline unsigned int get( unsigned int x )
 {
  x ^= x << 13;
     x ^= x >> 17;
     x ^= x << 5;
     return s = x; 
 }
 int ask( int x, int k )
 {
  if( !k )
   return x;
  x = fa[ x ][ g[ k ] ];
  k -= 1 << g[ k ];
  k -= dep[ x ] - dep[ top[ x ] ];
  x = top[ x ];
  return k >= 0 ? up[ x ][ k ] : down[ x ][ -k ];
 }
 void Fakemain( )
 {
  IOS;
  cin >> n >> q >> s;
  g[ 0 ] = -1;
  For( i, 1, n )
  {
   cin >> fa[ i ][ 0 ];
   if( fa[ i ][ 0 ] )
    v[ fa[ i ][ 0 ] ].push_back( i ); 
   else
    rt = i;
   g[ i ] = g[ i >> 1 ] + 1; 
  }
  Dfs( rt );
  Dfs( rt, rt );
  int ans = 0;
  long long ANS = 0;
  for( int i = 1; i <= q; ++i )
  {
   int x = ( get( s ) ^ ans ) % n + 1;
   int k = ( get( s ) ^ ans ) % dep[ x ];
   ANS ^= 1LL * i * ( ans = ask( x, k ) );
  }
  cout << ANS;
  return;
 }

} // namespace Solution

int main( int argc, char* argv[] )
{
 Solution::Fakemain( );
 return 0;
}