2023.12.5 cf 1902E
字典树的功能
根据字典树的概念，我们可以发现：字典树的本质是把很多字符串拆成单个字符的形式，以树的方式存储起来。所以我们说字典树维护的是”字典“。那么根据这个最基本的性质，我们可以由此延伸出字典树的很多妙用。简单总结起来大体如下：
1、维护字符串集合（即字典）。
2、向字符串集合中插入字符串（即建树）。
3、查询字符串集合中是否有某个字符串（即查询）。
4、统计字符串在集合中出现的个数（即统计）。
5、将字符串集合按字典序排序（即字典序排序）。
6、求集合内两个字符串的LCP（Longest Common Prefix，最长公共前缀）（即求最长公共前缀）。
本题思路
先算出所有组合不折叠的长度ans，之后再慢慢减去折叠长度
先插入建树，再查询字符串的反转（reverse），将折叠长度转化为LCP，减去LCP乘以2即可
踩过的坑
如果结点下标起始你设为0，那要注意一些值为0的东西对题目的影响（最好设成1算了），比如本题中的query，因为可能会遇到ch[i][j]为0，这样会导致p回到0，所以一定要break，但如果你的根下标为1就没有这个必要，因为0此时和任何字符都没有连接，ch[0][k]永远都是0，没有影响。
代码
#include<iostream>//以根下标为0举例，最好用1还是
#include<string>
#include<algorithm>
using namespace std;
#define ll long long
const int N=1000005;
int ch[N][30],cnt[N];
string s[N];
int idx;
ll ans=0;
void insert(string s)
{
int p=0;
for(auto c:s)
{
int j=c-'a';
if(!ch[p][j])ch[p][j]=++idx;
p=ch[p][j];
cnt[p]++;
}
}
void query(string s)
{
int p=0;
for(auto c:s)
{
int j=c-'a';
if(!ch[p][j])break;
p=ch[p][j];
ans-=2*cnt[p];
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>s[i];
ans+=s[i].length();
insert(s[i]);
}
ans*=n*2;
for(int i=1;i<=n;i++)
{
reverse(s[i].begin(),s[i].end());
query(s[i]);
}
cout<<ans<<endl;
return 0;
}