| 题目名称 | 2622. [HZOI 2016][NBUT 1653]String in the tree |
|---|---|
| 输入输出 | balsuffix.in/out |
| 难度等级 | ★★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 12 |
| 题目来源 |
 半汪
于2017-03-02加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：10， 提交：23， 通过率：43.48% | ||||
 Xiejiadong |
100 | 0.647 s | 6.90 MiB | C++ |
 半汪 |
100 | 0.755 s | 0.98 MiB | C++ |
 FoldingPaper |
100 | 0.773 s | 1.25 MiB | C++ |
|
FoldingPaper |
100 | 0.798 s | 1.25 MiB | C++ |
 _Itachi |
100 | 0.806 s | 12.88 MiB | C++ |
|
6666 |
100 | 0.810 s | 12.88 MiB | C++ |
 zcysky |
100 | 0.860 s | 5.37 MiB | C++ |
|
zcysky |
100 | 0.862 s | 6.89 MiB | C++ |
 小一米 |
100 | 0.911 s | 0.95 MiB | C++ |
 FoolMike |
100 | 0.998 s | 5.37 MiB | C++ |
| 关于 String in the tree 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
回复 @sxysxy :
陈立杰讲的SAM是按势摊还构造的，你要是持久化那岂不是随便卡！？ FoolMike
2017-08-24 07:40
6楼
| ||||
|
真·可持久化后缀自动机。
QAQ要不是多组数据...n = 1W轻松ac... | ||||
|
这题是后缀平衡树?
 chad
2017-04-21 10:45
4楼
| ||||
|
替罪羊居然比splay快这么多！真是难以置信！
| ||||
|
splay真慢- -
| ||||
|
| ||||
sxysxy2622. [HZOI 2016][NBUT 1653]String in the tree
★★★ 输入文件：balsuffix.in
输出文件：balsuffix.out
简单对比时间限制：1 s 内存限制：128 MiB
【题目描述】
一棵根节点为1的树，每个节点代表一个字符
对于每个节点求这个节点到根节点路径上的不同子串的个数
【输入格式】
第一行给出一个T为数据组数
对于每一组
第一行输入一个N，表示节点个数
之后的N-1行给出了u和v表示u、v之间有一条边
之后一行给出了一个长度为n的字符串，表示第i个节点代表的字符为s[i]
【输出格式】
对于每组数据，输出出N个数，表示节点i到根节点路径上的不同子串的个数。
【样例输入】
3 3 1 2 2 3 abc 3 1 2 2 3 aaa 3 1 2 2 3 aab
【样例输出】
1 3 6 1 2 3 1 2 5
【提示】
N<=10000,T<=20,都为小写字母，数据都为随机数据
【来源】
nbut1653，推荐一下可爱的OJ。