【hash】Similarity of Subtrees

图片来源：

https://blog.csdn.net/dylan_frank/article/details/78177368

 

 

 

【题意】：

　　对于每一个节点来说有多少对相同的子树。

【题解】：

　　利用层数进行hash，返回到对应的节点，最后标记后用等差数列来求出所有方案数。

 

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull ;

const int N = 1e5+10;
const ull p = 9901 ;

vector<int> G[N];
map < ull , int > Mp ;
ull Hash[N];

void dfs( int u , int Fa ){
    Hash[u] = 1 ;
    for( auto To : G[u] ){
        dfs( To , u ) ;
        Hash[u] = ( Hash[u] +  Hash[To] * p ) ;
    }
    Mp[ Hash[u] ] ++;
}

int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL) , cout.tie(NULL) ;

    int n ;
    cin >> n ;
    for( int i = 1 , u , v ; i < n ; i++ ){
        cin >> u >> v ;
        G[u].push_back( v );
    }

    dfs( 1 , 0 );
    ull ans = 0 ;

    //map< ll , int > :: iterator it = Mp.begin();
    for( auto x : Mp){
        ull tmp = x.second ;
        ans += ( tmp - 1 ) * tmp / 2 ;
    }
    cout << ans << endl ;

    return 0 ;
}