题意

给出一棵树,树上的点有权值,任意选择两点路径上的点构成一个字符串,求本质不同的字符串个数。

分析

这道题目也算半道语文题吧。

题面的最后一句话表达了叶子结点不超过 \(20\) 个,你要是没看见这句话,那整道题目就没了。

任意链上的问题一个常规的转换思路就是,以某一个叶子结点为根,就会转换到自上而下的一条直链,且只会出现在一个叶子结点为根的树上。

于是,我们分别以每一个叶子结点为根,把自上而下的所有字符串插入 sam 。这里因为是多串,需要广义 sam 。

统计不同的子串个数,就是经典题了。

 


发表评论

电子邮件地址不会被公开。 必填项已用*标注