3899: 仙人掌树的同构题解

leaf posted @ 2015年4月29日 20:40 in 未分类 , 492 阅读

第一次写与仙人掌有关的题目,虽然不是动态XXX

这个题目很有趣,问你有多少个同构的仙人掌

首先,仙人掌的问题肯定是要转换成树的问题的,那么可以先找出所以的环,对于每个环新建一个点,向所以这个环上的点连边,把环的边去掉,为了方便,在其他树边上新建一个中点,好,这样就转换成了树,并且等价。

 

现在考虑要找一个点它是不动的,显然是直径的中心,它不可能和其他的点换,而且新构的树中心是唯一的。把它拎起来,变成有根树。

剩下的考虑一个点,如果它不是环上的,那么如果有K个子树完全相同,那么有K!种方案。怎么判树相同?可以sort一下暴力hash,从小到大标号。

如果是环的中心,那么它不能随便交换,要考虑环上轮换(非中心不用考虑),或者对称,这个是字符串的基础问题了。

 

然后要考虑如果中心是环的中心,要考虑轮换

 

注意:

扫描环的时候要考虑顺序

偶环的对称有两种情况,都可以转换成回文串问题

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter