結果
| 問題 |
No.2337 Equidistant
|
| コンテスト | |
| ユーザー |
👑  p-adic
|
| 提出日時 | 2023-06-04 11:38:38 |
| 言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 24,302 bytes |
| コンパイル時間 | 13,713 ms |
| コンパイル使用メモリ | 283,588 KB |
| 最終ジャッジ日時 | 2025-02-13 22:36:12 |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 2 WA * 26 |
ソースコード
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#define CERR( ANSWER ) cerr << ANSWER << "\n";
#else
#pragma GCC optimize ( "O3" )
#pragma GCC optimize( "unroll-loops" )
#pragma GCC target ( "sse4.2,fma,avx2,popcnt,lzcnt,bmi2" )
#define CERR( ANSWER )
#endif
#include <bits/stdc++.h>
using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
#define ATT __attribute__( ( target( "sse4.2,fma,avx2,popcnt,lzcnt,bmi2" ) ) )
#define TYPE_OF( VAR ) decay_t<decltype( VAR )>
#define UNTIE ios_base::sync_with_stdio( false ); cin.tie( nullptr )
#define CEXPR( LL , BOUND , VALUE ) constexpr LL BOUND = VALUE
#define CIN( LL , A ) LL A; cin >> A
#define ASSERT( A , MIN , MAX ) assert( ( MIN ) <= A && A <= ( MAX ) )
#define CIN_ASSERT( A , MIN , MAX ) CIN( TYPE_OF( MAX ) , A ); ASSERT( A , MIN , MAX )
#define GETLINE( A ) string A; getline( cin , A )
#define GETLINE_SEPARATE( A , SEPARATOR ) string A; getline( cin , A , SEPARATOR )
#define FOR( VAR , INITIAL , FINAL_PLUS_ONE ) for( TYPE_OF( FINAL_PLUS_ONE ) VAR = INITIAL ; VAR < FINAL_PLUS_ONE ; VAR ++ )
#define FOREQ( VAR , INITIAL , FINAL ) for( TYPE_OF( FINAL ) VAR = INITIAL ; VAR <= FINAL ; VAR ++ )
#define FOREQINV( VAR , INITIAL , FINAL ) for( TYPE_OF( INITIAL ) VAR = INITIAL ; VAR >= FINAL ; VAR -- )
#define FOR_ITR( ARRAY , ITR , END ) for( auto ITR = ARRAY .begin() , END = ARRAY .end() ; ITR != END ; ITR ++ )
#define REPEAT( HOW_MANY_TIMES ) FOR( VARIABLE_FOR_REPEAT , 0 , HOW_MANY_TIMES )
#define QUIT return 0
#define COUT( ANSWER ) cout << ( ANSWER ) << "\n"
#define RETURN( ANSWER ) COUT( ANSWER ); QUIT
#define SET_PRECISION( PRECISION ) cout << fixed << setprecision( PRECISION )
#define DOUBLE( PRECISION , ANSWER ) SET_PRECISION << ( ANSWER ) << "\n"; QUIT
template <typename T> inline T Absolute( const T& a ){ return a > 0 ? a : -a; }
template <typename T> inline T Residue( const T& a , const T& p ){ return a >= 0 ? a % p : ( a % p ) + p; }
#define POWER( ANSWER , ARGUMENT , EXPONENT ) \
static_assert( ! is_same<TYPE_OF( ARGUMENT ),int>::value && ! is_same<TYPE_OF( ARGUMENT ),uint>::value ); \
TYPE_OF( ARGUMENT ) ANSWER{ 1 }; \
{ \
TYPE_OF( ARGUMENT ) ARGUMENT_FOR_SQUARE_FOR_POWER = ( ARGUMENT ); \
TYPE_OF( EXPONENT ) EXPONENT_FOR_SQUARE_FOR_POWER = ( EXPONENT ); \
while( EXPONENT_FOR_SQUARE_FOR_POWER != 0 ){ \
if( EXPONENT_FOR_SQUARE_FOR_POWER % 2 == 1 ){ \
ANSWER *= ARGUMENT_FOR_SQUARE_FOR_POWER; \
} \
ARGUMENT_FOR_SQUARE_FOR_POWER *= ARGUMENT_FOR_SQUARE_FOR_POWER; \
EXPONENT_FOR_SQUARE_FOR_POWER /= 2; \
} \
} \
#define POWER_MOD( ANSWER , ARGUMENT , EXPONENT , MODULO ) \
ll ANSWER{ 1 }; \
{ \
ll ARGUMENT_FOR_SQUARE_FOR_POWER = ( MODULO + ( ( ARGUMENT ) % MODULO ) ) % MODULO; \
TYPE_OF( EXPONENT ) EXPONENT_FOR_SQUARE_FOR_POWER = ( EXPONENT ); \
while( EXPONENT_FOR_SQUARE_FOR_POWER != 0 ){ \
if( EXPONENT_FOR_SQUARE_FOR_POWER % 2 == 1 ){ \
ANSWER = ( ANSWER * ARGUMENT_FOR_SQUARE_FOR_POWER ) % MODULO; \
} \
ARGUMENT_FOR_SQUARE_FOR_POWER = ( ARGUMENT_FOR_SQUARE_FOR_POWER * ARGUMENT_FOR_SQUARE_FOR_POWER ) % MODULO; \
EXPONENT_FOR_SQUARE_FOR_POWER /= 2; \
} \
} \
#define FACTORIAL_MOD( ANSWER , ANSWER_INV , INVERSE , MAX_I , LENGTH , MODULO ) \
static ll ANSWER[LENGTH]; \
static ll ANSWER_INV[LENGTH]; \
static ll INVERSE[LENGTH]; \
{ \
ll VARIABLE_FOR_PRODUCT_FOR_FACTORIAL = 1; \
ANSWER[0] = VARIABLE_FOR_PRODUCT_FOR_FACTORIAL; \
FOREQ( i , 1 , MAX_I ){ \
ANSWER[i] = ( VARIABLE_FOR_PRODUCT_FOR_FACTORIAL *= i ) %= MODULO; \
} \
ANSWER_INV[0] = ANSWER_INV[1] = INVERSE[1] = VARIABLE_FOR_PRODUCT_FOR_FACTORIAL = 1; \
FOREQ( i , 2 , MAX_I ){ \
ANSWER_INV[i] = ( VARIABLE_FOR_PRODUCT_FOR_FACTORIAL *= INVERSE[i] = MODULO - ( ( ( MODULO / i ) * INVERSE[MODULO % i] ) % MODULO ) ) %= MODULO; \
} \
} \
// 通常の二分探索その１
// EXPRESSIONがANSWERの狭義単調増加関数の時、EXPRESSION >= TARGETを満たす最小の整数を返す。
// 広義単調増加関数を扱いたい時は等号成立の処理を消して続く>に等号を付ける。
#define BS1( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , TARGET ) \
static_assert( ! is_same<TYPE_OF( TARGET ),uint>::value && ! is_same<TYPE_OF( TARGET ),ull>::value ); \
ll ANSWER; \
{ \
ll VARIABLE_FOR_BINARY_SEARCH_L = MINIMUM; \
ll VARIABLE_FOR_BINARY_SEARCH_U = MAXIMUM; \
ANSWER = ( VARIABLE_FOR_BINARY_SEARCH_L + VARIABLE_FOR_BINARY_SEARCH_U ) / 2; \
ll VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH; \
while( VARIABLE_FOR_BINARY_SEARCH_L != VARIABLE_FOR_BINARY_SEARCH_U ){ \
VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH = ( EXPRESSION ) - ( TARGET ); \
CERR( VARIABLE_FOR_BINARY_SEARCH_L << "<=" << ANSWER << "<=" << VARIABLE_FOR_BINARY_SEARCH_U << ":" << EXPRESSION << "-" << TARGET << "=" << VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH ); \
if( VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH == 0 ){ \
break; \
} else { \
if( VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH > 0 ){ \
VARIABLE_FOR_BINARY_SEARCH_U = ANSWER; \
} else { \
VARIABLE_FOR_BINARY_SEARCH_L = ANSWER + 1; \
} \
ANSWER = ( VARIABLE_FOR_BINARY_SEARCH_L + VARIABLE_FOR_BINARY_SEARCH_U ) / 2; \
} \
} \
CERR( VARIABLE_FOR_BINARY_SEARCH_L << "<=" << ANSWER << "<=" << VARIABLE_FOR_BINARY_SEARCH_U << ":" << EXPRESSION << "-" << TARGET << ">=0" ); \
} \
// 通常の二分探索その２
// EXPRESSIONがANSWERの狭義単調増加関数の時、EXPRESSION <= TARGETを満たす最大の整数を返す。
// 広義単調増加関数を扱いたい時は等号成立の処理を消して続く<に等号を付ける。
#define BS2( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , TARGET ) \
static_assert( ! is_same<TYPE_OF( TARGET ),uint>::value && ! is_same<TYPE_OF( TARGET ),ull>::value ); \
ll ANSWER; \
{ \
ll VARIABLE_FOR_BINARY_SEARCH_L = MINIMUM; \
ll VARIABLE_FOR_BINARY_SEARCH_U = MAXIMUM; \
ANSWER = ( VARIABLE_FOR_BINARY_SEARCH_L + VARIABLE_FOR_BINARY_SEARCH_U ) / 2; \
ll VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH; \
while( VARIABLE_FOR_BINARY_SEARCH_L != VARIABLE_FOR_BINARY_SEARCH_U ){ \
VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH = ( EXPRESSION ) - ( TARGET ); \
CERR( VARIABLE_FOR_BINARY_SEARCH_L << "<=" << ANSWER << "<=" << VARIABLE_FOR_BINARY_SEARCH_U << ":" << EXPRESSION << "-" << TARGET << "=" << VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH ); \
if( VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH == 0 ){ \
break; \
} else { \
if( VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH < 0 ){ \
VARIABLE_FOR_BINARY_SEARCH_L = ANSWER; \
} else { \
VARIABLE_FOR_BINARY_SEARCH_U = ANSWER - 1; \
} \
ANSWER = ( VARIABLE_FOR_BINARY_SEARCH_L + 1 + VARIABLE_FOR_BINARY_SEARCH_U ) / 2; \
} \
} \
CERR( VARIABLE_FOR_BINARY_SEARCH_L << "<=" << ANSWER << "<=" << VARIABLE_FOR_BINARY_SEARCH_U << ":" << EXPRESSION << "-" << TARGET << "<=0" ); \
} \
// 通常の二分探索その３
// EXPRESSIONがANSWERの狭義単調減少関数の時、EXPRESSION >= TARGETを満たす最大の整数を返す。
// 広義単調増加関数を扱いたい時は等号成立の処理を消して続く>に等号を付ける。
#define BS3( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , TARGET ) \
static_assert( ! is_same<TYPE_OF( TARGET ),uint>::value && ! is_same<TYPE_OF( TARGET ),ull>::value ); \
ll ANSWER; \
{ \
ll VARIABLE_FOR_BINARY_SEARCH_L = MINIMUM; \
ll VARIABLE_FOR_BINARY_SEARCH_U = MAXIMUM; \
ANSWER = ( VARIABLE_FOR_BINARY_SEARCH_L + VARIABLE_FOR_BINARY_SEARCH_U ) / 2; \
ll VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH; \
while( VARIABLE_FOR_BINARY_SEARCH_L != VARIABLE_FOR_BINARY_SEARCH_U ){ \
VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH = ( EXPRESSION ) - ( TARGET ); \
CERR( VARIABLE_FOR_BINARY_SEARCH_L << "<=" << ANSWER << "<=" << VARIABLE_FOR_BINARY_SEARCH_U << ":" << EXPRESSION << "-" << TARGET << "=" << VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH ); \
if( VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH == 0 ){ \
break; \
} else { \
if( VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH > 0 ){ \
VARIABLE_FOR_BINARY_SEARCH_L = ANSWER; \
} else { \
VARIABLE_FOR_BINARY_SEARCH_U = ANSWER - 1; \
} \
ANSWER = ( VARIABLE_FOR_BINARY_SEARCH_L + 1 + VARIABLE_FOR_BINARY_SEARCH_U ) / 2; \
} \
} \
CERR( VARIABLE_FOR_BINARY_SEARCH_L << "<=" << ANSWER << "<=" << VARIABLE_FOR_BINARY_SEARCH_U << ":" << EXPRESSION << "-" << TARGET << ">=0" ); \
} \
// 通常の二分探索その４
// EXPRESSIONがANSWERの狭義単調減少関数の時、EXPRESSION <= TARGETを満たす最小の整数を返す。
// 広義単調増加関数を扱いたい時は等号成立の処理を消して続く<に等号を付ける。
#define BS4( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , TARGET ) \
static_assert( ! is_same<TYPE_OF( TARGET ),uint>::value && ! is_same<TYPE_OF( TARGET ),ull>::value ); \
ll ANSWER; \
{ \
ll VARIABLE_FOR_BINARY_SEARCH_L = MINIMUM; \
ll VARIABLE_FOR_BINARY_SEARCH_U = MAXIMUM; \
ANSWER = ( VARIABLE_FOR_BINARY_SEARCH_L + VARIABLE_FOR_BINARY_SEARCH_U ) / 2; \
ll VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH; \
while( VARIABLE_FOR_BINARY_SEARCH_L != VARIABLE_FOR_BINARY_SEARCH_U ){ \
VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH = ( EXPRESSION ) - ( TARGET ); \
CERR( VARIABLE_FOR_BINARY_SEARCH_L << "<=" << ANSWER << "<=" << VARIABLE_FOR_BINARY_SEARCH_U << ":" << EXPRESSION << "-" << TARGET << "=" << VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH ); \
if( VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH == 0 ){ \
break; \
} else { \
if( VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH < 0 ){ \
VARIABLE_FOR_BINARY_SEARCH_U = ANSWER; \
} else { \
VARIABLE_FOR_BINARY_SEARCH_L = ANSWER + 1; \
} \
ANSWER = ( VARIABLE_FOR_BINARY_SEARCH_L + VARIABLE_FOR_BINARY_SEARCH_U ) / 2; \
} \
} \
CERR( VARIABLE_FOR_BINARY_SEARCH_L << "<=" << ANSWER << "<=" << VARIABLE_FOR_BINARY_SEARCH_U << ":" << EXPRESSION << "-" << TARGET << "<=0" ); \
} \
// 二進法の二分探索
// EXPRESSIONがANSWERの狭義単調増加関数の時、EXPRESSION <= TARGETを満たす最大の整数を返す。
#define BBS( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , TARGET ) \
ll ANSWER = MINIMUM; \
{ \
ll VARIABLE_FOR_POWER_FOR_BINARY_SEARCH = 1; \
ll VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH = ( MAXIMUM ) - ANSWER; \
while( VARIABLE_FOR_POWER_FOR_BINARY_SEARCH <= VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH ){ \
VARIABLE_FOR_POWER_FOR_BINARY_SEARCH *= 2; \
} \
VARIABLE_FOR_POWER_FOR_BINARY_SEARCH /= 2; \
ll VARIABLE_FOR_ANSWER_FOR_BINARY_SEARCH = ANSWER; \
while( VARIABLE_FOR_POWER_FOR_BINARY_SEARCH != 0 ){ \
ANSWER = VARIABLE_FOR_ANSWER_FOR_BINARY_SEARCH + VARIABLE_FOR_POWER_FOR_BINARY_SEARCH; \
VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH = ( EXPRESSION ) - ( TARGET ); \
if( VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH == 0 ){ \
VARIABLE_FOR_ANSWER_FOR_BINARY_SEARCH = ANSWER; \
break; \
} else if( VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH < 0 ){ \
VARIABLE_FOR_ANSWER_FOR_BINARY_SEARCH = ANSWER; \
} \
VARIABLE_FOR_POWER_FOR_BINARY_SEARCH /= 2; \
} \
ANSWER = VARIABLE_FOR_ANSWER_FOR_BINARY_SEARCH; \
} \
// 圧縮用
#define TE template
#define TY typename
#define US using
#define ST static
#define IN inline
#define CL class
#define PU public
#define OP operator
#define CE constexpr
#define CO const
#define NE noexcept
#define RE return
#define WH while
#define VO void
#define VE vector
#define LI list
#define BE begin
#define EN end
#define SZ size
#define MO move
#define TH this
#define CRI CO int&
#define CRUI CO uint&
#define CRL CO ll&
inline CEXPR( int , bound_NQ , 200000 );
list<int> edge[bound_NQ] = {};
inline list<int> E( const int& i ) { return edge[i]; }
// Resetはm_foundとm_prevを初期化
// Shiftはm_foundとm_prevを非初期化
#define DECLARATION_OF_FIRST_SEARCH( BREADTH ) \
template <int V_max,list<int> E(const int&)> \
class BREADTH ## FirstSearch \
{ \
\
private: \
int m_V; \
int m_init; \
list<int> m_next; \
bool m_found[V_max]; \
int m_prev[V_max]; \
\
public: \
inline BREADTH ## FirstSearch( const int& V ); \
inline BREADTH ## FirstSearch( const int& V , const int& init ); \
\
inline void Reset( const int& init ); \
inline void Shift( const int& init ); \
\
inline const int& size() const; \
inline const int& init() const; \
inline bool& found( const int& i ); \
inline const int& prev( const int& i ) const; \
\
int Next(); \
\
}; \
#define DEFINITION_OF_FIRST_SEARCH( BREADTH , PUSH ) \
template <int V_max,list<int> E(const int&)> inline BREADTH ## FirstSearch<V_max,E>::BREADTH ## FirstSearch( const int& V ) : m_V( V ) , m_init() , m_next() , m_found() , m_prev() { for( int i = 0 ; i < m_V ; i++ ){ m_prev[i] = -1; } } \
template <int V_max,list<int> E(const int&)> inline BREADTH ## FirstSearch<V_max,E>::BREADTH ## FirstSearch( const int& V , const int& init ) : BREADTH ## FirstSearch( V ) { m_init = init; m_next.push_back( m_init ); m_found[m_init] = true; } \
\
template <int V_max,list<int> E(const int&)> inline void BREADTH ## FirstSearch<V_max,E>::Reset( const int& init ) { m_init = init; assert( m_init < m_V ); m_next.clear(); m_next.push_back( m_init ); for( int i = 0 ; i < m_V ; i++ ){ m_found[i] = i == m_init; m_prev[i] = -1; } } \
template <int V_max,list<int> E(const int&)> inline void BREADTH ## FirstSearch<V_max,E>::Shift( const int& init ) { m_init = init; assert( m_init < m_V ); m_next.clear(); if( ! m_found[m_init] ){ m_next.push_back( m_init ); m_found[m_init] = true; } } \
\
template <int V_max,list<int> E(const int&)> inline const int& BREADTH ## FirstSearch<V_max,E>::size() const { return m_V; } \
template <int V_max,list<int> E(const int&)> inline const int& BREADTH ## FirstSearch<V_max,E>::init() const { return m_init; } \
template <int V_max,list<int> E(const int&)> inline bool& BREADTH ## FirstSearch<V_max,E>::found( const int& i ) { assert( i < m_V ); return m_found[i]; } \
template <int V_max,list<int> E(const int&)> inline const int& BREADTH ## FirstSearch<V_max,E>::prev( const int& i ) const { assert( i < m_V ); return m_prev[i]; } \
\
template <int V_max,list<int> E(const int&)> \
int BREADTH ## FirstSearch<V_max,E>::Next() \
{ \
\
if( m_next.empty() ){ \
\
return -1; \
\
} \
\
const int i_curr = m_next.front(); \
m_next.pop_front(); \
list<int> edge = E( i_curr ); \
\
while( ! edge.empty() ){ \
\
const int& i = edge.front(); \
bool& found_i = found( i ); \
\
if( ! found_i ){ \
\
m_next.PUSH( i ); \
m_prev[i] = i_curr; \
found_i = true; \
\
} \
\
edge.pop_front(); \
\
} \
\
return i_curr; \
\
} \
DECLARATION_OF_FIRST_SEARCH( Depth );
DEFINITION_OF_FIRST_SEARCH( Depth , push_front );
template <int V_max,list<int> E(const int&),int digit = 0>
class DepthFirstSearchOnTree :
public DepthFirstSearch<V_max,E>
{
private:
// メモリが厳しい場合、以下で不要なものを消す。
int m_reversed[V_max];
list<int> m_children[V_max];
bool m_set_children;
int m_depth[V_max];
int m_height[V_max];
bool m_set_height;
int m_weight[V_max];
bool m_set_weight;
int m_doubling[digit][V_max];
bool m_set_doubling;
public:
inline DepthFirstSearchOnTree( const int& V , const int& root );
inline void Reset( const int& init ) = delete;
inline void Shift( const int& init ) = delete;
inline const int& Root() const;
inline const int& Parent( const int& i ) const;
inline const list<int>& Children( const int& i );
inline const int& Depth( const int& i ) const;
inline const int& Height( const int& i );
inline const int& Weight( const int& i );
// 各ノードの高さ < 2^digitの時のみサポート。
int Ancestor( int i , int n );
int LCA( int i , int j );
int LCA( int i , int j , int& i_prev , int& j_prev );
private:
void SetChildren();
void SetHeight();
void SetWeight();
// 各ノードの高さ < 2^digitの時のみサポート。
// LCA()を呼ぶ前にAncestor()経由で完全にダブリングを設定するため、
// 遅延評価する../../../../Mathematics/Function/Iteration/Doubling/のダブリングで代用しない。
void SetDoubling();
};
template <int V_max,list<int> E(const int&),int digit> inline DepthFirstSearchOnTree<V_max,E,digit>::DepthFirstSearchOnTree( const int& V , const int& root ) :
DepthFirstSearch<V_max,E>( V , root ) , m_reversed() , m_children() , m_set_children() , m_depth() , m_height() , m_set_height() , m_weight() , m_set_weight() , m_doubling() , m_set_doubling()
{
int n = DepthFirstSearch<V_max,E>::size();
while( --n >= 0 ){
const int& i = m_reversed[n] = DepthFirstSearch<V_max,E>::Next();
const int& j = Parent( i );
if( j != -1 ){
m_depth[i] = m_depth[j] + 1;
}
}
}
template <int V_max,list<int> E(const int&),int digit> inline const int& DepthFirstSearchOnTree<V_max,E,digit>::Root() const { return DepthFirstSearch<V_max,E>::init(); }
template <int V_max,list<int> E(const int&),int digit> inline const int& DepthFirstSearchOnTree<V_max,E,digit>::Parent( const int& i ) const { return DepthFirstSearch<V_max,E>::prev( i ); }
template <int V_max,list<int> E(const int&),int digit> inline const list<int>& DepthFirstSearchOnTree<V_max,E,digit>::Children( const int& i ) { if( ! m_set_children ){ SetChildren(); } return m_children[i]; }
template <int V_max,list<int> E(const int&),int digit> inline const int& DepthFirstSearchOnTree<V_max,E,digit>::Depth( const int& i ) const { return m_depth[i]; }
template <int V_max,list<int> E(const int&),int digit> inline const int& DepthFirstSearchOnTree<V_max,E,digit>::Height( const int& i ) { if( ! m_set_height ){ SetHeight(); } return m_height[i]; }
template <int V_max,list<int> E(const int&),int digit> inline const int& DepthFirstSearchOnTree<V_max,E,digit>::Weight( const int& i ) { if( ! m_set_weight ){ SetWeight(); } return m_weight[i]; }
template <int V_max,list<int> E(const int&),int digit>
int DepthFirstSearchOnTree<V_max,E,digit>::Ancestor( int i , int n )
{
if( ! m_set_doubling ){
SetDoubling();
}
if( ( n >> digit ) != 0 ){
return Root();
}
int d = 0;
while( n != 0 ){
( ( n & 1 ) == 1 ) ? i = m_doubling[d++][i] : i;
n >>= 1;
}
return i;
}
template <int V_max,list<int> E(const int&),int digit>
int DepthFirstSearchOnTree<V_max,E,digit>::LCA( int i , int j )
{
int diff = Depth( i ) - Depth( j );
if( diff < 0 ){
swap( i , j );
diff *= -1;
}
i = Ancestor( i , diff );
if( i == j ){
return i;
}
int d = digit;
while( --d >= 0 ){
const int ( &doubling_d )[V_max] = m_doubling[d];
const int& doubling_d_i = doubling_d[i];
const int& doubling_d_j = doubling_d[j];
if( doubling_d_i != doubling_d_j ){
i = doubling_d_i;
j = doubling_d_j;
}
}
return Parent( i );
}
template <int V_max,list<int> E(const int&),int digit>
int DepthFirstSearchOnTree<V_max,E,digit>::LCA( int i , int j , int& i_prev , int& j_prev )
{
if( i == j ){
i_prev = j_prev = -1;
return i;
}
int diff = Depth( i ) - Depth( j );
if( diff < 0 ){
return LCA( j , i , j_prev , i_prev );
}
if( diff > 0 ){
i_prev = Ancestor( i , diff - 1 );
i = Parent( i_prev );
if( i == j ){
j_prev = -1;
return i;
}
} else if( ! m_set_doubling ){
SetDoubling();
}
int d = digit;
while( --d >= 0 ){
const int ( &doubling_d )[V_max] = m_doubling[d];
const int& doubling_d_i = doubling_d[i];
const int& doubling_d_j = doubling_d[j];
if( doubling_d_i != doubling_d_j ){
i = doubling_d_i;
j = doubling_d_j;
}
}
i_prev = i;
j_prev = j;
return Parent( i_prev );
}
template <int V_max,list<int> E(const int&),int digit>
void DepthFirstSearchOnTree<V_max,E,digit>::SetChildren()
{
assert( !m_set_children );
m_set_children = true;
const int& V = DepthFirstSearch<V_max,E>::size();
for( int i = 0 ; i < V ; i++ ){
const int& parent_i = Parent( i );
if( parent_i != -1 ){
m_children[parent_i].push_back( i );
}
}
return;
}
template <int V_max,list<int> E(const int&),int digit>
void DepthFirstSearchOnTree<V_max,E,digit>::SetHeight()
{
assert( !m_set_height );
m_set_height = true;
const int& V = DepthFirstSearch<V_max,E>::size();
for( int i = 0 ; i < V ; i++ ){
const int& reversed_i = m_reversed[i];
const int& parent_i = Parent( reversed_i );
if( parent_i != -1 ){
int& height_parent_i = m_height[parent_i];
const int& height_i = m_height[reversed_i];
height_parent_i > height_i ? height_parent_i : height_parent_i = height_i + 1;
}
}
return;
}
template <int V_max,list<int> E(const int&),int digit>
void DepthFirstSearchOnTree<V_max,E,digit>::SetWeight()
{
assert( !m_set_weight );
m_set_weight = true;
const int& V = DepthFirstSearch<V_max,E>::size();
for( int i = 0 ; i < V ; i++ ){
const int& reversed_i = m_reversed[i];
const int& parent_i = Parent( reversed_i );
if( parent_i != -1 ){
m_weight[parent_i] += m_weight[reversed_i] + 1;
}
}
return;
}
template <int V_max,list<int> E(const int&),int digit>
void DepthFirstSearchOnTree<V_max,E,digit>::SetDoubling()
{
assert( !m_set_doubling );
m_set_doubling = true;
const int& V = DepthFirstSearch<V_max,E>::size();
{
int ( &doubling_0 )[V_max] = m_doubling[0];
const int& r = Root();
for( int i = 0 ; i < V ; i++ ){
doubling_0[i] = i == r ? r : Parent( i );
}
}
for( int d = 1 ; d < digit ; d++ ){
int ( &doubling_d )[V_max] = m_doubling[d];
int ( &doubling_d_minus )[V_max] = m_doubling[d-1];
for( int i = 0 ; i < V ; i++ ){
doubling_d[i] = doubling_d_minus[doubling_d_minus[i]];
}
}
return;
}
int main()
{
UNTIE;
CIN_ASSERT( N , 2 , bound_NQ );
CIN_ASSERT( Q , 1 , bound_NQ );
int N_minus = N - 1;
REPEAT( N_minus ){
CIN_ASSERT( A , 1 , N );
CIN_ASSERT( B , 1 , N );
A--;
B--;
edge[A].push_back( B );
edge[B].push_back( A );
}
static DepthFirstSearchOnTree<bound_NQ,E,15> dfs{ N , 0 };
REPEAT( Q ){
CIN_ASSERT( S , 1 , N );
CIN_ASSERT( T , 1 , N );
S--;
T--;
int depth_S = dfs.Depth( S );
int depth_T = dfs.Depth( T );
int diff = depth_S - depth_T;
if( diff < 0 ){
swap( S , T );
swap( depth_S , depth_T );
diff *= -1;
}
if( S == T ){
COUT( N );
} else if( diff % 2 == 1 ){
COUT( 0 );
} else if( diff == 0 ){
int S_prev;
int T_prev;
dfs.LCA( S , T , S_prev , T_prev );
COUT( N - dfs.Weight( S_prev ) - dfs.Weight( T_prev ) - 2 );
} else {
int LCA = dfs.LCA( S , T );
int centre_prev = dfs.Ancestor( S , depth_S - 1 - dfs.Depth( LCA ) );
const int& centre = dfs.Parent( centre_prev );
COUT( dfs.Weight( centre ) - dfs.Weight( centre_prev ) );
}
}
QUIT;
}