#line 2 "tree/tree-hash.hpp"
#line 2 "tree/centroid.hpp"
#include <utility>
#include <vector>
using namespace std ;
template < typename G >
vector < int > centroid ( const G & g ) {
const int N = ( int ) g . size ();
vector < pair < int , int > > st ;
st . emplace_back ( 0 , - 1 );
vector < int > sz ( N ), par ( N );
while ( ! st . empty ()) {
auto p = st . back ();
if ( sz [ p . first ] == 0 ) {
sz [ p . first ] = 1 ;
for ( auto & to : g [ p . first ])
if ( to != p . second ) st . emplace_back ( to , p . first );
} else {
for ( auto & to : g [ p . first ])
if ( to != p . second ) sz [ p . first ] += sz [ to ];
par [ p . first ] = p . second ;
st . pop_back ();
}
}
vector < int > ret ;
int size = N ;
for ( int i = 0 ; i < N ; i ++ ) {
int val = N - sz [ i ];
for ( auto & to : g [ i ])
if ( to != par [ i ]) val = max ( val , sz [ to ]);
if ( val < size ) size = val , ret . clear ();
if ( val == size ) ret . emplace_back ( i );
}
return ret ;
}
#line 2 "tree/rooted-tree-hash.hpp"
#include <array>
#include <chrono>
#include <random>
#line 7 "tree/rooted-tree-hash.hpp"
using namespace std ;
#line 2 "internal/internal-hash.hpp"
namespace internal {
using i64 = long long ;
using u64 = unsigned long long ;
using u128 = __uint128_t ;
template < int BASE_NUM = 2 >
struct Hash : array < u64 , BASE_NUM > {
using array < u64 , BASE_NUM >:: operator [];
static constexpr int n = BASE_NUM ;
Hash () : array < u64 , BASE_NUM > () {}
static constexpr u64 md = ( 1ull << 61 ) - 1 ;
constexpr static Hash set ( const i64 & a ) {
Hash res ;
fill ( begin ( res ), end ( res ), cast ( a ));
return res ;
}
Hash & operator += ( const Hash & r ) {
for ( int i = 0 ; i < n ; i ++ )
if ((( * this )[ i ] += r [ i ]) >= md ) ( * this )[ i ] -= md ;
return * this ;
}
Hash & operator += ( const i64 & r ) {
u64 s = cast ( r );
for ( int i = 0 ; i < n ; i ++ )
if ((( * this )[ i ] += s ) >= md ) ( * this )[ i ] -= md ;
return * this ;
}
Hash & operator -= ( const Hash & r ) {
for ( int i = 0 ; i < n ; i ++ )
if ((( * this )[ i ] += md - r [ i ]) >= md ) ( * this )[ i ] -= md ;
return * this ;
}
Hash & operator -= ( const i64 & r ) {
u64 s = cast ( r );
for ( int i = 0 ; i < n ; i ++ )
if ((( * this )[ i ] += md - s ) >= md ) ( * this )[ i ] -= md ;
return * this ;
}
Hash & operator *= ( const Hash & r ) {
for ( int i = 0 ; i < n ; i ++ ) ( * this )[ i ] = modmul (( * this )[ i ], r [ i ]);
return * this ;
}
Hash & operator *= ( const i64 & r ) {
u64 s = cast ( r );
for ( int i = 0 ; i < n ; i ++ ) ( * this )[ i ] = modmul (( * this )[ i ], s );
return * this ;
}
Hash operator + ( const Hash & r ) { return Hash ( * this ) += r ; }
Hash operator + ( const i64 & r ) { return Hash ( * this ) += r ; }
Hash operator - ( const Hash & r ) { return Hash ( * this ) -= r ; }
Hash operator - ( const i64 & r ) { return Hash ( * this ) -= r ; }
Hash operator * ( const Hash & r ) { return Hash ( * this ) *= r ; }
Hash operator * ( const i64 & r ) { return Hash ( * this ) *= r ; }
Hash operator - () const {
Hash res ;
for ( int i = 0 ; i < n ; i ++ ) res [ i ] = ( * this )[ i ] == 0 ? 0 : md - ( * this )[ i ];
return res ;
}
friend Hash pfma ( const Hash & a , const Hash & b , const Hash & c ) {
Hash res ;
for ( int i = 0 ; i < n ; i ++ ) res [ i ] = modfma ( a [ i ], b [ i ], c [ i ]);
return res ;
}
friend Hash pfma ( const Hash & a , const Hash & b , const i64 & c ) {
Hash res ;
u64 s = cast ( c );
for ( int i = 0 ; i < n ; i ++ ) res [ i ] = modfma ( a [ i ], b [ i ], s );
return res ;
}
Hash pow ( long long e ) {
Hash a { * this }, res { Hash :: set ( 1 )};
for (; e ; a *= a , e >>= 1 ) {
if ( e & 1 ) res *= a ;
}
return res ;
}
static Hash get_basis () {
static auto rand_time =
chrono :: duration_cast < chrono :: nanoseconds > (
chrono :: high_resolution_clock :: now (). time_since_epoch ())
. count ();
static mt19937_64 rng ( rand_time );
Hash h ;
for ( int i = 0 ; i < n ; i ++ ) {
while ( isPrimitive ( h [ i ] = rng () % ( md - 1 ) + 1 ) == false )
;
}
return h ;
}
private:
static u64 modpow ( u64 a , u64 b ) {
u64 r = 1 ;
for ( a %= md ; b ; a = modmul ( a , a ), b >>= 1 ) r = modmul ( r , a );
return r ;
}
static bool isPrimitive ( u64 x ) {
for ( auto & d : vector < u64 > { 2 , 3 , 5 , 7 , 11 , 13 , 31 , 41 , 61 , 151 , 331 , 1321 })
if ( modpow ( x , ( md - 1 ) / d ) <= 1 ) return false ;
return true ;
}
static inline constexpr u64 cast ( const long long & a ) {
return a < 0 ? a + md : a ;
}
static inline constexpr u64 modmul ( const u64 & a , const u64 & b ) {
u128 d = u128 ( a ) * b ;
u64 ret = ( u64 ( d ) & md ) + u64 ( d >> 61 );
return ret >= md ? ret - md : ret ;
}
static inline constexpr u64 modfma ( const u64 & a , const u64 & b , const u64 & c ) {
u128 d = u128 ( a ) * b + c ;
u64 ret = ( d >> 61 ) + ( u64 ( d ) & md );
return ret >= md ? ret - md : ret ;
}
};
} // namespace internal
/**
* @brief ハッシュ構造体
* @docs docs/internal/internal-hash.md
*/
#line 10 "tree/rooted-tree-hash.hpp"
template < typename G >
struct RootedTreeHash {
using Hash = internal :: Hash < 1 > ;
const G & g ;
int n ;
vector < Hash > hash ;
vector < int > depth ;
static vector < Hash >& xs () {
static vector < Hash > _xs ;
return _xs ;
}
RootedTreeHash ( const G & _g , int root = 0 ) : g ( _g ), n ( g . size ()) {
hash . resize ( n );
depth . resize ( n , 0 );
while (( int ) xs (). size () <= n ) xs (). push_back ( Hash :: get_basis ());
dfs ( root , - 1 );
}
private:
int dfs ( int c , int p ) {
int dep = 0 ;
for ( auto & d : g [ c ]) {
if ( d != p ) dep = max ( dep , dfs ( d , c ) + 1 );
}
Hash x = xs ()[ dep ], h = Hash :: set ( 1 );
for ( auto & d : g [ c ]) {
if ( d != p ) h = h * ( x + hash [ d ]);
}
hash [ c ] = h ;
return depth [ c ] = dep ;
}
};
/**
* @brief 根付き木のハッシュ
*/
#line 5 "tree/tree-hash.hpp"
template < typename G >
vector < typename RootedTreeHash < G >:: Hash > tree_hash ( const G & g ) {
using Hash = typename RootedTreeHash < G >:: Hash ;
auto cs = centroid ( g );
if (( int ) cs . size () == 1 ) cs . push_back ( cs [ 0 ]);
vector < Hash > hs ;
for ( auto & c : cs ) hs . push_back ( RootedTreeHash { g , c }. hash [ c ]);
sort ( begin ( hs ), end ( hs ));
return hs ;
} 
tree/tree-hash.hpp