[AIZU2784]Similarity of Subtrees（树Hash）

Description

Define the depth of a node in a rooted tree by applying the following rules recursively:

    The depth of a root node is 0.
The depths of child nodes whose parents are with depth d are d+1


Let S(T,d) be the number of nodes of T with depth d. Two rooted trees T and T′ are similar if and only if S(T,d) equals S(T′,d) for all non-negative integer d
You are given a rooted tree Twith N nodes. The nodes of T are numbered from 1 to N. Node 1 is the root node of T. Let Ti be the rooted subtree of T whose root is node i. Your task is to write a program which calculates the number of pairs (i,j) such that Ti and Tj are similar and i<j.

解决思路

$Hash[u]=\sum Hash[v]*base$

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

#define ll long long
#define ull unsigned long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxN=101000;
const int maxM=maxN*2;
const ull base=20729;
const int inf=2147483647;

int n;
ull W[maxN];

void dfs(int u);

int main()
{
scanf("%d",&n);
for (int i=1;i<n;i++)
{
int a,b;scanf("%d%d",&a,&b);
}
dfs(1);
sort(&W[1],&W[n+1]);
ll Ans=0;
W[++n]=inf;
for (int i=1,j=0;i<=n;i++) if (W[i]!=W[j]) Ans=Ans+1ll*(ll)(i-1-j+1)*(ll)(i-1-j)/2,j=i;
printf("%lld\n",Ans);
return 0;
}

void dfs(int u)
{
W[u]=1;