【hash】Similarity of Subtrees

图片来源:

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

【hash】Similarity of Subtrees

【题意】:

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

【题解】:

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

 #pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull ; const int N = 1e5+;
const ull p = ; vector<int> G[N];
map < ull , int > Mp ;
ull Hash[N]; void dfs( int u , int Fa ){
Hash[u] = ;
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 = , u , v ; i < n ; i++ ){
cin >> u >> v ;
G[u].push_back( v );
} dfs( , );
ull ans = ; //map< ll , int > :: iterator it = Mp.begin();
for( auto x : Mp){
ull tmp = x.second ;
ans += ( tmp - ) * tmp / ;
}
cout << ans << endl ; return ;
}
上一篇:【hash】Seek the Name, Seek the Fame


下一篇:【hash】珍珠