2016弱校联盟十一专场10.3---Similarity of Subt…
2018-06-17 23:43:18来源:未知 阅读 ()
题目链接
https://acm.bnu.edu.cn/v3/problem_show.php?pid=52310
problem 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 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.
Input
The input consists of a single test case. N a1 b1 … 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.
Output
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. 14
Sample Input1
5
1 2
1 3
1 4
1 5
Output for the Sample Input 1
6
Sample Input2
6
1 2
2 3
3 4
1 5
5 6
Output for the Sample Input 2
2
Sample Input3
13
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
6 10
7 11
8 12
11 13
Output for the Sample Input 3
14
题意:输入一棵由n个点和n-1条边构成的树,求这个树中两棵相似的子树有多少对? 相似的子树:要求在相同的深度,两颗子树的在这一层的节点数相同;
思路:深搜,hash表示每一个点为子树时的子树状态;
第三组样例:对图上每个点,给一个标识p^d d为这个点的深度,那么每个点的子树状态就可以用子树上所有项的和表示,如2号节点p^4+2p^3+2p^2+p 3号节点p^4+2p^3+2p^2+p 它们的多项式相同,为了方便用map映射统计,可以给p赋一个值,为了减小冲突可以取一个较大的质数,这就是hash;
代码如下:
#include <iostream> #include <stdio.h> #include <queue> #include <string.h> #include <vector> #include <map> #include <string> #include <set> using namespace std; typedef long long LL; const LL maxn=1e6+10,p=9901,mod=1e9+7; vector<LL>G[maxn]; LL hash_v[maxn]; map<LL,LL>mp; map<LL,LL>::iterator it; void dfs(LL u) { hash_v[u]=1; for(LL i=0; i<G[u].size(); i++) { LL v=G[u][i]; dfs(v); hash_v[u]=(hash_v[u]+hash_v[v]*p)%mod; } mp[hash_v[u]]++; } int main() { ///freopen("in.txt","r",stdin); LL n; LL u,v; while(scanf("%lld",&n)!=-1) { for(LL i=0; i<=n; i++) G[i].clear(); mp.clear(); for(LL i=1; i<n; i++) { scanf("%lld%lld",&u,&v); G[u].push_back(v); } dfs(1); LL ans=0; for(it=mp.begin(); it!=mp.end(); it++) ans+=it->second*(it->second-1)/2; printf("%lld\n",ans); } return 0; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 2020年3月28日UCF Local Programming Contest 2016 2020-03-31
- 洛谷P4071-[SDOI2016]排列计数 题解 2020-01-12
- [NOIP2016]天天爱跑步-题解 2019-10-08
- CSP201612-2:工资计算 2018-09-05
- CSP201604-2:俄罗斯方块 2018-09-01
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash