| 题目名称 | 2607. [河南省队2016]九头蛇和时间 |
|---|---|
| 输入输出 | af_time.in/out |
| 难度等级 | ★★★☆ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 10 |
| 题目来源 |
 FoolMike
于2017-02-05加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：27， 提交：40， 通过率：67.5% | ||||
 yourfather |
100 | 0.215 s | 26.99 MiB | C++ |
|
yourfather |
100 | 0.235 s | 26.99 MiB | C++ |
|
yourfather |
100 | 0.239 s | 26.99 MiB | C++ |
|
yourfather |
100 | 0.242 s | 26.99 MiB | C++ |
|
yourfather |
100 | 0.245 s | 26.99 MiB | C++ |
|
ONCE AGAIN |
100 | 0.247 s | 26.99 MiB | C++ |
 _Itachi |
100 | 0.252 s | 10.99 MiB | C++ |
 L_in |
100 | 0.308 s | 11.76 MiB | C++ |
 Go灬Fire |
100 | 0.309 s | 14.62 MiB | C++ |
|
Go灬Fire |
100 | 0.312 s | 9.52 MiB | C++ |
| 关于 九头蛇和时间 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
trie上SA 不错哦
 再见
2017-06-17 12:32
8楼
| ||||
|
| ||||
|
超级大蒟蒻表示终于遇到个会做的题= =
记得去ZJOI2015诸神眷顾的幻想乡拿双倍经验 | ||||
|
身败名裂……
| ||||
 FoolMike
2017-02-14 12:31
4楼
| ||||
|
@FoolMike 请问您是广义后缀自动机么？？
 YGOI_真神名曰驴蛋蛋
2017-02-14 11:15
3楼
| ||||
|
[size=55]-1s!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!![/size]
 HZOI_蒟蒻一只
2017-02-08 20:41
2楼
| ||||
|
[size=55]暴力膜！！！！！！！！！！！！！！！！！！！！！！！！！[/size]
HZOI_蒟蒻一只
2017-02-08 20:39
1楼
| ||||
sxysxy
AntiLeaf【题目描述】
“……致力于人生而平等的理念……使此民有民治民享之政府永世长存……很惭愧，只做了一点微小的工作，谢谢大家。”
“好啊！”“支持！”“excited!”庆祝战斗胜利的人群发出一阵阵排山倒海般的掌声。
“嘿，”Fmuckss凑到正向台下人挥手的Asm.Def身边，“分析结果出来了。”
“九头蛇把宇宙魔方作为某种……通道，传送时间维本身，把一个人的时间维转移到另一个，从而成为不死者。”
“明白了，”Asm.Def若有所思地点点头，“砍掉一个头，还会生出两个。”
Fmuckss发现，九头蛇构建了一套高维通路，它们形成一棵由N个节点组成的树，节点编号为1~N，其中1是根。为了了解它转移时间的能力，Asm.Def想要计算，树中有多少条不同的祖先路径。祖先路径指某条路径A~B，以A为起点，B为终点，且B是A的祖先（包括A本身）。两条路径相同当且仅当它们的长度相同，而且相应节点的度数相同（即路径上节点的度数所组成的序列相同）。
【输入格式】
第一行一个整数N，代表节点个数。
接下来N-1行，每行两个数u,v，代表一条树边(u,v)。
【输出格式】
一行一个正整数，即不同的祖先路径条数。
【样例输入】
3 2 1 3 1
【样例输出】
3
【数据范围】
对于20%的数据，1<=N<=20
对于另外20%的数据，树是一条链，1是一个端点
对于另外30%的数据，1<=N<=1000
对于100%的数据，1<=N<=10^5
【来源】
2016河南省队集训，数据是Mike造的，如果数据有误请联系Mike，谁有官测直接刷掉就好。