老年人过来对着会的题口胡几发

B.腊肠披萨

题意翻译：给你n个小写字母串，求所有小写字母串两两之间的最长公共前缀的乘方和，对一个任意数取模。

比较显然的，看到多串公共前缀直接建Trie统计贡献。建好之后对每个串在Trie上走，每走一步加上当前子树内串个数和父子树内串个数之差，就能差分地求出乘方和。

（考场队友一直喊广义SAM吓得这边不敢开这题，过来一看发现是Trie板子，结果还是摸了11发摸不出来难绷）

C.DFS 序

题意翻译：给定一棵树，树上每个点有权值wi，求一个遍历顺序（DFS序，也就是便利队列pi）使得Σpiwi最大。

也是签到，考虑树形DP，DP上来之后是一个国王游戏的形式，算一下交换权是$\frac{W_i}{S_i}$，$W_i$，$S_i$分别是子树的权值和和子树大小。

然后按照这个顺序dp即可。

E. 循环赛

 结论题，观察数据猜测答案是：

z为1：奇2偶1，因为可以均分，这个特判就行。

否则答案形式：n为奇数，2*(n-z)+1，n为偶数，2*(n-z)+2，大概不需要证明

然后就过了。

G. Menji 和 gcd

 trick题，考虑分块：

L，R比较大的时候，gcd比较大的情况，x/gcd，y/gcd一定很小。

此时枚举gcd的倍数t，看x = R/t与 y = x*(t-1)是否同时在L，R范围内即可。

折半分块之后求最大gcd就行。

I. 不等式

显然的拓扑排序。

对每个整数，连两条边判环即可。

判完环之后进行最小构造输出即可。

J. 另一个计数问题

 好做但现场被我搞了没敲的题。

检查连通性：

若u,v都小于n/2，那么u,v必然联通。

这是因为u可以通过跳到2*u再跳到2。

这样，合数都联通，大于n/2的质数都被孤立。

再推一波式子，归根结底下来求n以内的质数和sum。

问题转化为求小于n的质数和sum。这是min25筛送分板子的一种。直接做就行了。

后面再慢慢update一下。