JAG Asia 2016-Similarity of Subtrees(BFS+哈希)

浅浅的花香味﹌ 2023-06-05 12:33 6阅读 0赞

### Similarity of Subtrees ###

时间限制: 1 Sec 内存限制: 128 MB

#### 题目描述 ####

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 T with 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.

#### 输入 ####

The input consists of a single test case.  
  
N  
a1 b1  
a2 b2  
...  
aN−1 bN−1  
  
The first line contains an integer N (1≤N≤100,000), which is the number of nodes in a tree. The following N−1 lines give information of branches: the i-th line of them contains ai and bi, which indicates that a node ai is a parent of a node bi. (1≤ai,bi≤N,ai≠bi) The root node is numbered by 1. It is guaranteed that a given graph is a rooted tree, i.e. there is exactly one parent for each node except the node 1, and the graph is connected.

#### 输出 ####

Print the number of the pairs (x,y) of the nodes such that the subtree with the root x and the subtree with the root y are similar and x<y.

## 样例输入 ##

5
    1 2
    1 3
    1 4
    1 5

#### 样例输出 ####

1 #include<bits/stdc++.h>
     2 #pragma GCC optimize(3)
     3 using namespace std;
     4 typedef long long ll;
     5 const int maxn=1e6+7;
     6 const ll prime=1e5+7;
     7 const ll mod=1e9+7;
     8 map<ll,ll>MAP;
     9 ll Hash_val[maxn];
    10 vector<int>vct[maxn];
    11 void bfs(int a)
    12 {
    13     Hash_val[a]=1;
    14     int siz=vct[a].size();
    15     for(int i=0;i<siz;++i)
    16     {
    17         int b=vct[a][i];
    18         bfs(b);
    19         Hash_val[a]=(Hash_val[a]+Hash_val[b]*prime)%mod;
    20     }
    21     MAP[Hash_val[a]]++;
    22 }
    23 int main()
    24 {
    25     int n;
    26     scanf("%d",&n);
    27     for(int i=1;i<n;++i)
    28     {
    29         int a,b;
    30         scanf("%d%d",&a,&b);
    31         vct[a].push_back(b);
    32     }
    33     ll ans=0;
    34     bfs(1);
    35     for(map<ll,ll>::iterator it=MAP.begin();it!=MAP.end();++it)
    36     {
    37         ans+=(it->second-1)*(it->second)/2;
    38     }
    39     printf("%lld\n",ans);
    40     return 0;
    41 }

转载于:https://www.cnblogs.com/CharlieWade/p/11449036.html