图片来源:
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+;
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 ;
}